01背包问题!只有小白才懂小白
01背包问题，是指每个物品只能用一次，求背包中的最大价值
我们该如何思考这些问题呢？
首先，我们能直接依次取最大价值的物品放进去吗？这是一种贪心的思想，肯定是行不通的。我们应该把每个物品逐个加进来.讨论里面的规律是什么。
假设背包的容量是c，第i个物品的价值是w[i]，它的体积是v[i]对于第i个物品，如果v[i]>c，第i个物品是放不进去的，所以它的最大价值是i-1件物品讨论时的最大价值；如果v[i] <= c，第i个物品能放进去，但是我们要不要把它装进我们的背包呢？如果装进背包，最大价值就是w[i] + (i-1件物品，背包容量为c - v[i]情况下的最大值) , 如果不装进去，最大价值就是i-1件物品讨论时的最大价值。
现在，我们用数组把上述文字表示一下 f[i][j] 表示的是第i件物品 , 容量为j时的最大价值 Ⅰ.w [i] > c时 ,f[i][j] = f[i-1][j]; Ⅱ.w[i] < c时 ①放第i个物品 f [i][j] = w[i] + f [i-1][j-v[i]] ②不放第i个物品 f[i][j] = f[i-1][j]; 所以状态方程为f[i][j] = max(f[i-1][j],f[i-1][j-v[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]) f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]); } }
根据状态转移方程，我们可以发现在f[i]这一层，只用到了f[i-1]这层，且状态转移方程中的 j, j-v[i]都是小于等于j的，并不是分布在j的两端，根据这两个特性，我们可以将二维优化成为一维。
如果我们直接将i这维删去的话，就会变成
for(int i = 1 ;i <= n ;i ++) for(int j = 0 ;j <= m ;j ++) { f[j] = f[j]; if(j >= v[i]) f[j] = max(f[j],f[j-v[i]] + w[i]); }
f[j] = f[j]; //这个恒成立，直接可以删去
因为if的判断条件是j >= v[i]，所有(0,v[i])范围的数没有意义
for循环中可以直接从j = v[i]开始
所以，我们接着可以修改为
for(int i = 1 ;i <= n ;i ++) for(int j = v[i] ;j <= c ;j ++) { f[j] = max(f[j],f[j-v[i]] + w[i]); }
那么f [ j ] = max(f [ j ],f [ j - v [ i ] ] + w [ i ] )就等价于f [ i ] [ j ] = max( f [ i - 1 ] [ j ] , f [ i - 1 ] [ j - v [ i ] ] ) 吗？
j从前往后模拟真的可行吗？
仔细想想，不难发现
假设当我们更新第i层状态的时候，f[j] = max(f[j],f[j-v[i]] + w[i])，当我们需要用到f[j-v[i]]时，因为j - v[i]是小于j的，所以j - v[i]的状态在j之前更新过了
f[j - v[i]]相当于是第i层中j - v[i]的值,即f[i][j - v[i]]，而状态转移方程中我们需要的是第i-1层中f[j - v[i]]，所以我们应该从后往前模拟，j > j - v[i]，所以j就会再j - v[i]之前更新，用到的j - v[i]的值还是第 i - 1层中的值
//一维模板 for(int i = 1; i <= n; i++) { for(int j = c; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]); }
讲了这么多，你可能还是有点糊涂，那么我们直接上个例子吧
例题
有 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
二维数组
解释一下这个表格怎么来的，横着的12345代表背包容量为j时的情况，竖着的abcd则是i个物品
模拟一下(c,3)点，即f[3][3]，第三个物品背包容量为3时的情况，f[3][3] = max(f[2][3],f[2][0]+4) = max(6,4) = 6
当我们计算f[2]时,f[2] = max(f[2],f[2-2] + 4) = 4,相当于取了一次b物品
当我们算f[4]时，又要用到f[2]，f[4] = max(f[4],f[4-2]+4) = max(2,4+4) = 8
我们在算f[2]中取了一次第二件物品，f[4]时又取了一次第二件物品，相当于在算f[4]时取了两次b物品，不符合01背包，所以我们应该从后往前模拟。顺带提一句，多重背包不计较物品取出的次数，这也可以解释多重背包为什么可以从前往后模拟。
代码
#include <iostream> #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[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0；
才学dp，也是第一次写复杂点的博客，有问题的话还请大家指出！
