0/1背包问题:_0/1背包问题: 现有n种物品,对1<=i<=n,已知第i种物品的重量为正整数wi,价值为正整

问题描述：

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

算法分析：

1..实现的目标：使得子集中物品的总重量不超过W且总价值尽量大。

2.限制的条件：包最大载重量是一定的，物品的个数是一定的。

3.实现的过程：对每种物品进行舍取。

4.实现的方法：递归。

对于第n个物品来说，我们对它有两种处理方式。

1.  放到背包中，我们用x[n]=1表示。

2.  由于条件限制，不能放到背包中，用x[n]=0表示。

重新审视一下，我们会发现，对这个物品处理完后，我们会发现我们遇到了相似的问题

1.  若物品放到了背包中，我们的任务变为：现在变成了有n-1种物品，背包能承受的最大载重量为正整数W-Wi,找到最优解。

2.  若物品没有放到背包中，我们的任务变为：现在变成了有n-1种物品，背包能承受的最大载重量为正整数W,找到最优解。

 

证明结论:

设函数KnapSack(n,m)来表示从n个物品中，背包的最大承重是m的条件限制下的最好方案的值 根据上述的两种情况我们可以列出下列等式：

递归调用的终结条件是背包的容量为0或物品的数量为0

下面我们来看看限制条件：

为什么我们会不选那个物品呢？因为选了它就不会得到最大值。就是说，

KnapSack(n,m)>KnapSack(n-1,m-Wn)+Vn;

程序实现:

intMake(int i, int j) 

{   

    int r1 = 0; 

    int r2 = 0; 

    int r = 0;

    if (i == -1) 

    { 

        return 0; 

    }

    if(j >= WEIGHT[i])   //背包剩余空间可以放下物品 i   

    { 

        r1 = Make(i-1,j - WEIGHT[i]) +VALUE[i]; //第i件物品放入所能得到的价值 

        r2 = Make(i-1,j); //第i件物品不放所能得到的价值   

        r = (r1>r2)?r1:r2; 

    } 

    return r; 

}