背包问题算法探究

有N个物品，其价值为数组W[]，重量为数组P[]，包的承重量为M，问包能承重的最大价值？

一、设F[i,j]为前i个物品放入承重为j的包的最大价值，那必然：

F[i,j] = Max{F[i-1,j],F[i-1,j-P[i]]+W[i]}

可能你会对此公式会有些疑问，为什么会得到此公式，那我们来讲解一下公式，前i个物品放入承重为j的包的最大价值只会存在两种情况：
（1）当不带第i件商品时，那么其最大价值为F[i-1,j]
（2）当带i件商品时，那么前i-1件商品放在剩余重量j-P[i]的最大价值,在加上第i件本身价值，为F[i-1,j-P[i]]+W[i]

二、如何将公式转化为可执行的代码
以下描述的是5个物品，其重量为{2,2,6,5,4}，价值为{6,3,5,4,6},承重为10的包的问题

beibao.png
eg：d9的单元格的值是：F[4,9] = Max{F[3,9]，F[3,9-5]+4} = Max{c9,c4 + 4} = Max{10,10} = 10
c10单元格的值是：F[3,10] = Max{F[2,10],F[2,10-6]+5} = Max{11,11} = 11

//C为包的承重，N为背包个数，w为物品重量，v为物品价值
    int maxinput(int C,int N ,int w[],int v[])  
    {  
        int[] V = new int[C+1];
        int i,j;   
        for(j=0;j<=C;j++)  
        {  V[j]=0;  
        }  
        for(i=0;i<N;i++)  
        {  
            for(j=C;j>=w[i];j--)  
            {  
                V[j]=max(V[j],V[j-w[i]]+v[i]);  
            }  
        }  
        return(V[C]);  
    }