01背包问题

有n个物品和一个容量为v的背包，每一个物品有两个属性（体积v，价值w），每件物品最多只用一次。在所有物品中选择的物品总体积最小（小于背包容量），价值最大。

利用动态规划解决。

相关题目

题目链接

原题链接

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0< N,V ≤1000
0 < vi,wi ≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

难度：简单

时/空限制：1s / 64MB

来源：背包九讲 , 模板题

算法标签

背包问题、DP

代码思路

二维代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int n , m;
int v[N] , w[N];
int f[N][N];

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++)
        cin >> v[i] >> w[i];

    //f[0][0~m]都是0，但由于f[][]是全局变量，初始化就是0，则i从1开始 ↓
    for(int i = 1;i <= n;i ++)
        for(int j = 0;j <= m;j ++)
        {
            f[i][j] = f[i-1][j];
            if(j >= v[i])
                f[i][j] = max(f[i][j] , f[i-1][j-v[i]]+w[i]);   
        }

    cout << f[n][m] << endl;

    return 0;
}

一维版

为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

例如，一维状态第i轮对体积为 3 的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该是f[i - 1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1][4]。

简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。

关于状态f[j]的补充说明
二维下的状态定义f[i][j]是前 i 件物品，背包容量 j 下的最大价值。一维下，少了前 i 件物品这个维度，我们的代码中决策到第 i 件物品（循环到第i轮），f[j]就是前i轮已经决策的物品且背包容量 j 下的最大价值。

因此当执行完循环结构后，由于已经决策了所有物品，f[j]就是所有物品背包容量 j 下的最大价值。即一维f[j]等价于二维f[n][j]。

该部分来源：【AcWing】 深蓝
链接：https://www.acwing.com/solution/content/1374/

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int n , m;
int v[N] , w[N];
int f[N];

int main()
{
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++)
		cin >> v[i] >> w[i];
		
		
	for(int i = 1;i <= n;i ++)
		for(int j = m;j >= v[i];j --)
		{
		//	f[i][j] = f[i-1][j];  一维状态下：f[j] = f[j]恒等式，删 
		//	if(j >= v[i])
			f[j] = max(f[j] , f[j - v[i]] + w[i]);	
		}
	
	cout << f[m] << endl;
	
	return 0;
}

//f[i][j]只用到了f[i-1][j]，则可以使用滚动数组 f[j] 

完全背包问题

有n个物品和一个容量为v的背包，每一个物品有两个属性（体积v，价值w），每件物品有无限个。

相关题目

原题链接

题目描述

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

难度：简单

时/空限制：1s / 64MB

总通过数：78845
总尝试数：140268

来源：背包九讲 , 模板题

算法标签

背包、问题DP

思路

朴素版（三维）

会超时

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N] , v[N];
int f[N][N];
int n , m;

int main()
{
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++)
		cin >> v[i] >> w[i];
		
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= m;j ++)
			for(int k = 0;k*v[i] <= j;k ++)
				f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
		
	cout << f[n][m] << endl;
	
	return 0;
}

二维优化版

转自【AcWing 】Charles__

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N] , v[N];
int f[N][N];
int n , m;

int main()
{
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++)
		cin >> v[i] >> w[i];
		
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= m;j ++)
			{
				f[i][j] = f[i-1][j];
				
				if(j - v[i] >= 0)
					f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
			}
		
	cout << f[n][m] << endl;
	
	return 0;
}

一维优化版

根据二位优化版，可以看出与01背包问题类似，则可以根据01背包问题进行优化

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N] , v[N];
int f[N];
int n , m;

int main()
{
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++)
		cin >> v[i] >> w[i];
		
	for(int i = 1;i <= n;i ++)
		for(int j = v[i];j <= m;j ++)
				f[j] = max(f[j],f[j-v[i]]+w[i]);
			
		
	cout << f[m] << endl;
	
	return 0;
}

多重背包问题

有n个物品和一个容量为v的背包，每一个物品有两个属性（体积v，价值w），每个物品最多有s[i]个

朴素版

题目链接

原题链接

题目描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100
0<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

难度：简单

时/空限制：1s / 64MB

来源：背包九讲 , 模板题

算法标签

背包问题、DP

思路

与完全背包类似

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N] , w[N] , s[N];
int f[N][N];
int n , m;

int main()
{
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++)
		cin >> v[i] >> w[i] >> s[i];
	
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= m;j ++)
			for(int k = 0;k <= s[i] && k*v[i] <= j;k ++)
				f[i][j] = max(f[i][j] , f[i-1][j-k*v[i]]+k*w[i]);
	
	cout << f[n][m] << endl;
	
	
	return 0;
}

优化

分组背包问题

有n组物品，每组物品有若干个，每组最多选1个