问题描述:
我们有n种物品，物品j的重量为wj，价格为vj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。[1]
解题思路：
最终的目标是在总重量不超过W的前提下，总价值最高。在总重量不操作Y的前提下，我们可以将前j种物品的总价值所能达到的最高值定义为value[j][Y]；那么就会有:
value[0][Y] = 0; //Y=[0,1,2,...,W]
value[j][0] = 0; //j=[1,2,...,n]
如果Wj > Y， value[j][Y] = value[j-1][Y]; //这时Wj不能放入背包，所以总价值还是等于前一个物品放入时的价值
如果Wj <= Y，value[j][Y] = MAX(value[j-1][Y]，vj + alue[j-1][Y-Wj]); // 这时就得分两种情况来分析，一种是当前状态下不能再放入，另一种情况时放入进去；然后从这两种情况里面选最大值
通过计算value[n][W]就可以得到最终的结果。（上面的注释分析是我自己的理解方法，也不知道对不对，但是按照这种方法我自己能够比较好的理解这个问题）
最后，再确定累加计算的方式，那么这个问题就顺利的实现出来了。我们可以针对每一个j值（此时的j表示的时前j个物品都放入到背包里面），都遍历一遍背包的所以可能容量(0,1,2,...,W)，即用两个for循环即可。可以用下面这个图来辅助理解：[2]
h横坐标表示的是Y的值，0—10，纵坐标表示的是物品的个数1—3。
代码实现：
#include <stdio.h> #define MAX_LEN 100 #define MAX(a,b) ((a) > (b) ? (a) : (b)) int value[MAX_LEN][MAX_LEN]; //value[i][j]表示总重量不超过j时，前i个物品所能构成的最大价值 int w[]={-1,3,4,5}; //物品重量数组 int v[]={-1,4,5,6}; //物品价值数组 int package(int m, int n); int main() { int m,n,i,j; int ret; m = 10; //背包容量 n = 3; //物品个数 //scanf("%d%d",&m,&n); for (i = 0; i <= m; i++) for (j = 0; j <= n; j++) value[i][j] = 0; ret = package(m,n); printf("%d ",ret); return 0; } int package(int m, int n) { int i,j; for (j = 1; j <= n; j++) //背包编号 { for (i = 0; i <= m; i++) //背包容量 { if (w[j] <= i) { value[j][i] = MAX(value[j-1][i],v[j] + value[j-1][i-w[j]]); } else { value[j][i] = value[j-1][i]; } } } return value[n][m]; } 2013/10/11 23:31
参考文档：
[2] 百度文库里面的文章 http://wenku.baidu.com/view/7d0ebd8ccc22bcd126ff0ce2.html