算法设计与分析关于多重背包问题

0-1背包问题描述

考虑将n个物体分别具有重量w₁到wₙ以及价值v₁到vₙ的情况，并有一个能够承受总重量W的背包。如何选择这些物品放入其中而不超过其承载能力，并使得所选子集的价值最大化？

0-1背包解题思路

递推式

    F(i,j)=max{F(i-1,j-kwi)+k*vi}
    k=0,1
    i=[0,n]
    j=[o,W]

F(i,j)表示前 i 个物体(1≤ i ≤n）在背包承重为 j 时，所能达到的最大价值。如果把它看成一个状态的话，那么也就是说，状态F(i,j)的值等于状态F(i-1,j)、状态F(i-1,j-wi)与vi之和 两者中的最大值。那么要求 i 个物体在一定承重背包中可取的最大价值，只需考虑 i-1 个物体在不同承重量（0，1， 2， …，W）的背包下可取的最大价值。类似地，要想知道 i-1 个物体在一定承重的背包中可取的最大价值，只需知道 i-2 个物体在不同承重量的背包中可取的最大价值。以此类推，直到所考虑的物体个数变为 1。
所以，只要我们知道物体个数为 1 时，在不同承重量的背包中所能取到的最大价值，就可以依次求物体个数为2,3，…，n的情况下在不同承重量的背包中所能取的最大价值

0-1背包实现代码

    int max(int a,int b){