0/1背包问题:

现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W_i，价值为正整数V_i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）

根据问题描述，可以将其转化为如下的约束条件和目标函数：

于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。

0-1背包问题可以看作是寻找一个序列，对任一个变量 的判断是决定=1还是=0.在判断完之后，已经确定了，在判断时，会有两种情况：

（1）          背包容量不足以装入物品i，则=0，背包的价值不增加；

（2）          背包的容量可以装下物品i，则=1，背包的价值增加。

这两种情况下背包的总价值的最大者应该是对判断后的价值。令表示在前i个物品中能够装入容量为j的背包的物品的总价值，则可以得到如下的动态规划函数：

     式（1）说明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0.式（2）第一个式子说明：如果第i个物品的重量大于背包的容量，则装入第i个物品得到的最大价值和装入第i-1个物品得到的最大价值是相同的，即物品i不能装入背包中；第二个式子说明：如果第i个物品的重量小于背包的容量，则会有两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为的背包中的价值加上第i个物品的价值；（2）如果第i个物品没有装入背包，则背包中物品的价值就是等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

     我们可以一步一步的解出我们所需要的解。第一步，只装入第一个物品，确定在各种情况下背包能得到的最大价值；第二步，只装入前两个物品，确定在各种情况下的背包能够得到的最大价值；依次类推，到了第n步就得到我们所需要的最优解了。最后，便是在容量为W的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从的值向前寻找，如果>,说明第n个物品被装入了背包中，前n-1个物品被装入容量为的背包中；否则，第n个物品没有装入背包中，前n-1个物品被装入容量为W的背包中。依此类推，直到确定第一个物品是否被装入背包为止。由此，我们可以得到如下的函数：.

     根据动态规划函数，用一个的二维数组C存放中间变量，表示把前i个物品装入容量为j的背包中获得的最大价值。

以下为一个例子

     假设最大容量M=10，物品个数N=3，物品大小w{3,4,5}，物品价值p{4,5,6}。

从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

代码：

#include<iostream>
#include<algorithm>
#include <vector>
#include<string.h>
#include<ctype.h>
#include<math.h>
using namespace std;
const int n=3;   //物品数量
const int W=10;  //背包容量
int c[n+1][W+1];
void DP(int v[], int w[])
{
	int i,j;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			if (w[i] > j)
				c[i][j] = c[i-1][j];
			else
				c[i][j]=max(c[i-1][j-w[i]]+ v[i],c[i-1][j]);
		}
	}
}
int main()
{
	int w[4]={0,3,4,5};
	int v[4]={0,4,5,6};
	memset(c,0,sizeof(c));
	DP(v,w);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=W;j++)
			printf("%-3d ",c[i][j]);
		puts("");
	}
}

运行结果如图：

这里是用二位数组存储的，可以把空间优化，用一维数组存储。

用c[0..j]表示，c[j]表示把前i件物品放入容量为j的背包里得到的价值。把i从1~n(n件)循环后，最后f[j]表示所求最大值。

*这里c[j]就相当于二位数组的c[i][j]。那么，如何得到c[i-1][j]和c[i-1][j-w[i]]+w[j]？（重点！思考）
首先要知道，我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即：for i=1..N
现在思考如何能在是c[j]表示当前状态是容量为j的背包所得价值，而又使c[j]和c[j-w[i]]+w[i]表示前一状态的价值？

逆序！

#include<iostream>
#include<algorithm>
#include <vector>
#include<string.h>
#include<ctype.h>
#include<math.h>
using namespace std;
const int n=3;   //物品数量
const int W=10;  //背包容量
int c[W+1];
void DP(int v[], int w[])
{
	int i,j;
	for (int i = 1; i <= n; i++)
	{
		for (int j = W; j >=0; j--)
		{
			if(j>=w[i])
				c[j]=max(c[j-w[i]]+ v[i],c[j]);
			printf("%-3d ",c[j]);
		}
		cout<<endl;
	}
}
int main()
{
	int w[4]={0,3,4,5};
	int v[4]={0,4,5,6};
	memset(c,0,sizeof(c));
	DP(v,w);
}

0/1背包问题（动态规划）