先上题目：
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 背包问题， 先来把最容易想到的动态规划算法写出来。
我们设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下的最大价值
其实最为简单的一种解法是：把每种物品的个数确认下来，然后当作不同物品，这样就转换成了0-1背包问题。
比如 A B C三类物品，背包分别最多放3个A物品，2个B物品，或 2个C物品。
那么问题变成: a1, a2, a3, b1, b2, c1, c2 共7个物品，只能取一次。
这样算法的复杂度为 n*W*k, 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下的最大价值（1） 找出最佳递推方程。
（2） 敲写代码，完成算法。
其他背包变种：
【大家明白才是真的明白】从0-1背包到无限制背包，到背包变种。,布布扣,bubuko.com
【大家明白才是真的明白】从0-1背包到无限制背包，到背包变种。
原文：http://blog.csdn.net/tbwood/article/details/22728109