有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]);
}
