问题描述
给定N个物品和一个背包，背包的容量为W， 假设背包容量范围在[0，15]，第i个物品对应的体积和价值分别为W[i]和v[i]。各种物品的价值和重量如下：
物品编号 1 2 3 4 5
重量W 3 4 7 8 9
价值V 4 5 10 11 13
解题思路
动态规划原理：是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法方法。0/1背包问题可以看作是决策一个序列（x1,x2,x3,x4,….xn）,对任一变量xi的决策是决定xi=1，还是xi=0。在对xi-1决策后，已确定了（x1,x2,x3,x4,….xi-1），在决策xi时，问题处于两种状态之一：
背包容量不足以装入物品i，则xi=0，背包不增加价值；
背包容量可以装入物品i，则xi=1，背包价值增加了 vi；
这两种情况下背包价值的最大者应该是对xi决策后的背包价值。
令v（i，j）表示装载前i种物品，总重量不超过j时背包的最大价值
面对当前商品有两种可能性：
包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；
由此可以得出递推关系式：
j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝
根据递推公式,可以逐步求出当物品数为 i ,背包容量为 j 时的背包最大总价值，
但在求解之前，要将边界初始化
显然的 v(0,j)=0，v(i,0)=0
构造最优解
通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，可以通过最优解回溯找出解的组成：
我们可以声明一个长度为6的数组content[6]来标记物品是否选取，content[1]~content[5]分别对应物品1到物品5，将数组初始化为0，
1表示选取该物品，0表示不选取
V(i,j)=V(i-1,j) 或者 j - w[i] <0 时，说明没有选择第i 个商品，则回到V(i-1,j)；
否则即说明装了第i个商品，该商品是最优解组成的一部分，content[i]=1，然后回到V(i-1,j-w(i))；
一直遍历到i＝0结束为止,我们能找到所有解的组成
(ps:对我来说,单纯看理论概念很容易烦躁而且很难理解，通过源代码结合概念能够有更清晰的认识）
源代码：
/*本关任务：给定N个物品和一个背包，背包的容量为W， 假设背包容量范围在[0，15]，第i个物品对应的体积和价值分别为W[i]和v[i]。各种物品的价值和重量如下：
物品编号 1 2 3 4 5
重量W 3 4 7 8 9
价值V 4 5 10 11 13
求: 如何选择装入背包的物品，使得装入背包的物品的总价值为最大.
*/
#include <stdio.h>
int content[6]={0}; //最优解的物品组成
int w[6]={0,3,4,7,8,9}; //物品对应的重量
int v[6]={0,4,5,10,11,13}; //物品对应的价值
int bV=15; //背包的最大容量为15
int maxVal[6][16]={0}; //存放当物品数为i,背包容量为j的最大总价值
void findContent(int i, int j); //找到最优解的物品组成
void findMax(); //寻找当物品数为i,背包容量为j时的最大总价值
void print(); //打印最优解物品组成
int main( void )
{
int i,j;
printf("当物品数为i,背包容量为j时的能装入背包的最大总价值\n");
findMax();
for (int i=0;i<6;i++) //打印当物品数为i,背包容量为j时的最大总价值
{
for(int j=0;j<16;j++)
{
printf("%2d ",maxVal[i][j]);
}
printf("\n");
}
printf("请输入当前的物品数：");
scanf("%d",&i);
printf("请输入当前背包的最大容量: ");
scanf("%d",&j);
findContent(i,j);
printf("最优解的物品组成为： \n");
for (int k = 1; k < 6; k++)
{
if(content[k])
printf("价值为 %d ,重量为 %d 的 %d 号物品\n",v[k],w[k],k);
}
printf("物品数为%d 背包容量为 %d时的最大总价值为 %d\n",i,j,maxVal[i][j]);
return 0;
}
void findMax() //寻找当物品数为i,背包容量为j时的最大总价值
{
for(int i=1;i<6;i++)
for(int j=1;j<16;j++)
{
if (j < w[i]) //如果背包容量小于物品i重量，表示背包存放不下第i种物品,此时的最大总价值为i-1种物品的最大总价值
maxVal[i][j] = maxVal[i - 1][j];
else
{
if(maxVal[i-1][j]>(maxVal[i-1][j-w[i]]+v[i]))//放下第i种物品时的总价值为第i种物品的价值加上当物品数为i-1背包容量为j-w[i]的最优解
maxVal[i][j]=maxVal[i-1][j]; // 对比当放下第i种物品时的总价值和物品数位i-1时的总价值，取最大值
else
maxVal[i][j]=maxVal[i-1][j-w[i]]+v[i];
}
}
}
void findContent(int i, int j) { //最优解组成
if (i > 0 )
{
if (maxVal[i][j] == maxVal[i - 1][j] || j - w[i] <0)
{
content[i] = 0;
findContent(i - 1, j);
}
else
{
content[i] = 1;
findContent(i - 1, j - w[i]);
}
}
}
运行结果