01背包的问题很早就想写了，但是因为一些意外的事情耽搁了下来今天补习一下01背包问题的计算过程。
首先，01背包的问题大致如下：
一个已知承重大小的背包，我们将要在其中放入物品，已知一系列物品的重量和价值，求解怎样把物品装入背包中使背包中物品的总价值最大。
解题思路如下：
假设该背包的承重为a，物体的重量是w，价值为v，那么：
1、如果a<w，那么这个物体是不能被放入背包中的。
2、如果a<w，该物体可以被放在背包中，我们需要判断是不是应该被放在背包中。
1）如果被放在背包中，那么放入该物体后背包中物体的总价值即等于承重量为a-w的背包所放置的物品价值之和再加上该物体的价值。
2）如不放在背包里，那么背包内的物品总价值不变。
判断是否需要把物品放在背包里的条件为：
在承重量为a-w的背包所放置的物品价值加上该物品的价值得出的总价值是否大于不装这个物品时的价值总数。
如果是，那么需要添加本物品，否则不添加。
因此我们需要知道承重为0-a的背包的物品放置放置方案。
如图为承重量是10的背包中如何放置5个已知价值和重量的物品的放置方案。表格的阅读方式应为从下往上，从左向右，在第2列，表示当背包容量是2的情况下的物品放置方案。从下往上看，当只能放置e物品时，重量4>2，所以不放置，背包内的价值数为0，当再放置第d个物品时，5>2，物品不能放进去，那么价值数还为0；到再放物品b时，2==2，那么该物体被放入背包，背包内的价值总为3。到此放置物品a的时候，由于2==2，所以比较是否放置后价值会变高，可放置的总重量是2，2-2=0，即当承重为0的背包放置的物品价值加上该物品本身价值的和，承重为0的背包价值自然为0，0+6=6，6>3，所以应当放置这个物品。依此类推，我们可以把这个表格填满，所求的可以放置的最大价值即为最后一列第一行的数据15。
到此，我们可以推断算法的实现方法。
首先，初始化一个二维数组用来存放表格内的数据c[N][M]。
然后，初始化每一个数据为0表示背包为空。
再从第一行开始初始化每一列的计算工作。遵循我们推测出来的公式：c[i][m]=max{c[i-1][m-w[i]]+pi , c[i-1][m]}
最后，取出c[N-1][M-1]的值，即承重最大时所有物品都可以放置的时候背包内物品价值的最大值。
根据以上推断，就可以写出相关代码了。
#include<stdio.h>
#include<stdlib.h>
int main(){
int n, m, i, j, max;
int c[100][100] = { 0 }, v[100] = { 0 }, w[100] = {0};
printf("第一个参数是一共有多少个物品\n第二个参数表示背包的承重量\n");
scanf_s("%d%d",&n,&m);
printf("两个参数指的分别是每件物品的重量和价值\n");
for (i = 0; i < n; i++){
scanf_s("%d%d",&w[i],&v[i]);
}
for (i = 1; i <= m; i++){
for (j = 0; j < n; j++){
if (w[j] > i){
if (j==0)
c[i][j] = 0;
else
c[i][j] = c[i][j - 1];
}
else{
if (j == 0)
max = v[j];
else{
max = c[i - w[j]][j - 1] + v[j];
if (max < c[i][j - 1])
max = c[i][j - 1];
}
c[i][j] = max;
}
}
}
printf("最大的价值为：%d\n",c[m][n-1]);
system("pause");
return 0;
}
在这里我们要注意的是，由于一共有n个物品，每个物品又只能放置一次，所以不能多次放置同一个物品，在比较重量为i-w[j]的背包所包含的最大价值时需要与未放置当前物品j的情况下的价值。所以在此max的值应赋为 c[i - w[j]][j - 1] + v[j]。
