问题背景
0-1背包
给定n个物品，考虑他们的重量 和 价值，分别为 w[0], w[1], w[2], w[3] … w[n-1] 和 v[0], v[1], v[2], v[3], v[4] … v[n-1]。 现在有一个载重量为 W 的背包，求这个背包能放入的物品组合的最大价值。（每个物品只有一件）。
物品数量无限制背包
给定n种物品，考虑各个种类的物品单件的 重量 和 价值，分别为 w[0], w[1], w[2], w[3] … w[n-1] 和 v[0], v[1], v[2], v[3], v[4] … v[n-1]。 现在有一个载重量为 W 的背包，求这个背包能放入的物品组合的最大价值。（每种物品数量无限，可以任意取）。
0-1背包问题解法
考虑0-1背包问题，先来把最容易想到的动态规划算法写出来。我们设d[i][j] 表示 前 i 个物品在背包容量为j下的最优价值。这时候，对于第 i个物品 （物品下标从 0开始），d[i+1][j]表示前i+1个物品(即第0号、第1号、……第i号) 在背包容量为j 下的最优价值。
NOTE: 前i+1个物品分别为 第0号、1号、……i个物品。在动态规划算法实现过程中，正确使用数组下标，可以节省很多控制代码。本算法中，大致规则为：如果使用正向推演（从第一个开始往后），那么需要把第0行数据初始化为0，即第0行代表前0个对象，价值显然为0；第一行代表前一个物品（即第0号物品）。如果使用逆向推演（从最后一个开始往前），那么需要把最后一行（第n行）数据初始化为0，即第0行代后（n-0=n）个物品，第n行代表后（n-n=0）个物品（不存在），价值显然也为0。这样下面的 i+1，w[i] 就好理解了
我们已经知道了 前 i 个物品(即第0号、第1号、……第i-1号)的最优解，为 d[i][j], 0<= j <= W 考虑第i号物品 潜在选择方案有两种： (1) 如果不放入这号物品，那么显然 d[i+1][j] = d[i][j] ； (2) 如果放入这号物品，那么 d[i+1][j] = d[i][j-w[i]]+v[i]; 那么，什么情况下要放入这号物品呢？什么时候不放呢？ 首先要看看w[i]是否比j大，如果比j大，那么背包放不下，就不用考虑了，肯定不放了，d[i+1][j] = d[i][j]。 如果w[i] <= j，那么背包能放下，就需要考虑放还是不放了，先放进去看看价值 d[i][j-w[i]]+v[i]的大小，再看看不放进去的大小d[i][j]，然后取大的那个作为最优值即可。 递推关系式如下：
d[i+1][j]=d[i][j] w[i]>j
d[i+1][j]=max(d[i][j], d[i][j-w[i]]+v[i] ) w[i]≤j
代码如下：
int w[n];//重量
int v[n];//价值
int d[n+1][W+1];//memset初始化为0
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
if(w[i]>j)
d[i+1][j]= d[i][j];
else
d[i+1][j] = max(d[i][j],d[i][j-w[i]]+v[i]);
cout<< d[n][W]; //前n个物品在背包重量为W下的最大价值
数量无限制背包问题
物品数量无限制背包： 给定n种物品，考虑各个种类的物品单件的 重量 和 价值，分别为 w[0], w[1], w[2], w[3] … w[n-1] 和 v[0], v[1], v[2], v[3], v[4] … v[n-1]。 现在有一个载重量为 W 的背包，求这个背包能放入的物品组合的最大价值。（每种物品数量无限，可以任意取）。 其实最为简单的一种解法是：把每种物品的个数确认下来，然后当作不同物品，这样就转换成了0-1背包问题。 比如 A B C三类物品，背包分别最多放3个A物品，2个B物品，或 2个C物品。 那么问题变成: a1, a2, a3, b1, b2, c1, c2 共7个物品，只能取一次。 这样算法的复杂度为 nWk, k和W是线性关系 k= ?*W,所以 复杂度为 nWW, 复杂度有点高。 看下面这种思考方式： 若在 d[i+1][j] 取最优时，背包含有2个第i号物品，那么在 d[i+1][j-w[i]] 取最优时，背包必然含有1个第i号物品。 证明：反正法 如果在d[i+1][j-w[i]]取得最优时，背包不含有第i号物品，且在d[i+1][j]取得最优值时，背包含有两个第i号物品。 那么当d[i+1][j]取得最优时，扣掉一个第i号物品，d’[i+1][j-w[i]] 将不是最优的，因为里面还有第i号物品，那么这时候我们用最优的 d[i+1][j-w[i]] （不含有第i号物品）来加上一个第i号物品，应当获得的d’[i+1][j]更大，这和d[i+1][j]已经是最优值相矛盾。 有了这种思维方式，可以知道，在考虑同一种物品时，d[i+1][j] = max (d[i+1][j-w[i]] +v[i], d[i][j]); 这句话的意思是，直观的方案有两种： （1） 一个第i号物品都不放，也就是 d[i+1][j]=d[i][j]； （2） 装入k个第i号物品。若，选择 装入k个第i号物品 时 d[i+1][j] 最优，那么在d[i+1][j-w[i]]最优时，背包肯定含有k-1个第i号物品（上面证明过）。所以 d[i+1][j]=d[i+1][j-w[i]] +v[i]； 其实还有一种可行方案： （3） 装入1个第i号物品。d[i+1][j] = d[i][j-w[i]] +v[i]；这样一来， d[i+1][j] = max (d[i+1][j-w[i]] +v[i], d[i][j-w[i]] +v[i]，d[i][j]);其实，d[i+1][j-w[i]]必然是大于或者等于 d[i][j-w[i]]的，所以才简化为： d[i+1][j] = max (d[i+1][j-w[i]] +v[i], d[i][j]); 这种递推方法要求，d[i+1][j-w[i]] 在d[i+1][j] 前先被更新，所以，j的循环递增方向应该是从小->大。 这时候，我们可以写出无限制背包问题的算法代码。
int w[n];//重量
int v[n];//价值
int d[n+1][W+1];//memset初始化为0
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
if(j<w[i])
d[i+1][j] = d[i][j];
else
d[i+1][j] = max(d[i][j],d[i+1][j-w[i]]+v[i]);
cout<< d[n][W]; //前n种物品在背包重量为W下的最大价值
d[i+1][j] = d[i][j];
else
d[i+1][j] = max(d[i][j],d[i+1][j-w[i]]+v[i]);
cout<< d[n][W]; //前n种物品在背包重量为W下的最大价值
要解决背包问题以及其他变种背包问题，通用策略为： （1） 找出最佳递推方程。 （2） 敲写代码，完成算法。 其他背包变种： 在0-1背包中，加入限制条件：总选择的物品数目为 M。（提示：算法复杂度 nWM） 在无限制背包中，加入限制条件：总选择的物品数目为M。（提示：算法复杂度 nWM）