本文主要总结我对背包问题学习的心得，主要是把我以前在印象笔记中的内容搬了过来。
先给出常见的背包情形：
01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。
我们现在主要是求解0-1背包，就是只有单副本的情形，并且只求价值的最大，没有多余的限制条件诸如必须背包装满时的最大价值。
还是对于怎么考虑这个问题我不做太多说明，参看下面的链接。 [利用金矿模型理解背包] [本质是搜索的思想，只不过用打表存储子问题的解]
下面我直接给出DP求解时的，四个关键点。 状态f[ i ][ j ]：从前i个物品中选择若干件，让入承重为j的背包中所能达到的最大价值。 状态转移函数：f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] ); 初始化：f[ i ][ 0 ] = 0 , i from 0 to N f[ 0 ][ j ] = 0 j from to M（这里有bug等会说） 结果：f[ N ][ M ]
补充：有助于理解 算法基本思想： 利用动态规划思想 ，子问题为：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。 其状态转移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} //这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。 解释一下上面的方程：“将前i件物品放入容量为v的背包中”这个子问题，如果只考虑第i件物品放或者不放，那么就可以转化为只涉及前i-1件物品的问题， 即1、如果不放第i件物品，则问题转化为“前i-1件物品放入容量为v的背包中”； 2、如果放第i件物品，则问题转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”(此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i])。 则f[i][v]的值就是1、2中最大的那个值。
对于bug的说明：之所以是bug是因为这种条件并不通用。下面分析一下，这个bug搞了我一晚上。 就是对于初始化这么分析， 如果物品N==0，那么一件物品都没有，价值肯定为0.所以f[ 0 ][ i ] = 0; 对于，背包的容量来说，按照常理如果背包的容量M==0。那么价值也一定为0，因为什么都放不进去，所以不会有价值。f[ i ][ 0 ] = 0;也就是说，这种情况下默认的是所有物品的容量都大于0。
但是，偏偏存在这样的情况就是，人为假设存在容量为0的物品。那么当j==0时，这一列的值就不能被初始化为0了，因为把容量为0的物品放进去，此时就会有价值了。所形成的状态表就会不一样。
如果此时还是按照之前的方式初始化，就会出错。因为显然第0列的值都不一样了，肯定会错。 并且上面用理论给出了证明，第0列存在不为0的情形，只要存在容量为0的物品就好。
考虑这样一组输入： 背包容量为1，两个物品。其中第一个物品的容量为0。 value: 1 2 cost: 0 1
给出两种初始化的对比情况，只要你要明白一点。如果存在容量为0的物品，那么j==0时，这一列不能初始化为0.因为容量为0的物品可以放入容量为0的背包。导致价值不为0. 
第一个注意点（初始化考虑价值为0的物品）： 为了保证统一： 以后统统采用下面的形式，主要是修改了初始化的形式； 下面我直接给出DP求解时的，四个关键点。 状态-f[ i ][ j ]：从前i个物品中选择若干件，让入承重为j的背包中所能达到的最大价值。 状态转移函数：f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] ); 初始化：f[ i ][ 0 ] = 0 , i from 0 to N（只初始化第0行，因为什么物品都没有价值一定为0） 结果：f[ N ][ M ]
第二个注意点（小心下标对应不一致带来的问题。小心）： 对于转移方程： f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] )
上面公式中的w[i]和v[i]的意思是第i个物品的消耗和价值，默认下标是从1开始的。所以，如果下标不是从1开始开始。这两个点需要修正。f[i][j]不需要修正，是因为他们考虑了容量为0和物品为0的情形。
修正下标的情形： f[ i ][ j ] = max( f[ i - 1 ][ j - w[i-1] ] + v[i-1] , f[ i - 1 ][ j ] )
[采药]
没有修正下标，因为直接从1开始
#include <iostream>#include <cstring>#include <utility>#define N 1000 // 总时间#define M 100 // 物品种类int w[M + 1];int v[M + 1];int f[M+1][N+1];int knapsack( int n, int m );int main( void ){ int n = 0, m = 0; while(std::cin >> n >> m){ memset(w, 0 , sizeof(w)); memset( v, 0, sizeof(v) ); for( int i = 1; i <= m; ++i ){ std::cin >> w[i] >> v[i]; } int ans = knapsack( n, m ); std::cout << ans << std::endl; } return 0;}int knapsack( int n, int m ){ memset( f, 0, sizeof(f) ); for( int i = 0; i <= n; ++i ) f[0][i] = 0; for( int i = 1; i <= m; ++i ){ for( int j = 0; j <= n; ++j ){//j=0，因为物品容量可能为0 if( w[i] <= j ) f[i][j] = std::max( f[i-1][j] , f[i-1][j-w[i]] + v[i] ); else f[i][j] = f[i-1][j]; } } return f[m][n];}第三个注意点：空间优化的问题 考察转移方程： f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] ) 每一行的修正只与上一行有关，根据这个特点，我们可以将原本的二维数组优化为一维。并且，由于f[i][j]的修正只与上一行当中左侧的元素有关，所以可用如下方式完成状态的转移。并且从右至左更新。 dp[j] = max{ dp[j], dp[j-w[i]] + v[i] }
综上，这个背包问题可以用如下算法求解：
zero_one_pack(v[i],c[i]) for j = M to c[i] f[j] = max( f[j-c[i]]+v[i] , f[j] )f[0......M] = 0; // 初始化第0行，即一个物品都没有的情形。J一定要包括0.这是关键。for i = 1 to N zero_one_pack(v[i],w[i])上式当中，for j = M to c[i] 的优化很优雅。但是原始算法不能优化，因为全是0，还是需要把之前的值f[i-1][j]赋给f[i][j]，不然后者是0；变成滚动数组之后，就是原来的值。没必要再赋值一遍。
[采药]
参考这篇链接[lintcode-背包问题]
新闻热点
疑难解答
