问题描述
给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？
核心公式：
f[i][j]=max{f[i-1][j],f[i-1][j-A[i]]+A[i]}
不放第i个物品：f[i-1][j]
放第i个物品：那么问题就转化为“前i-1件物品放入剩下的容量为j-A[i]的背包中”，此时能获得的最大体积就是f[i-1][j-A[i]]再加上通过放入第i件物品获得的体积A[i]
代码
public int backPackII(int m, int[] A, int[] V) {
// write your code here
int[][] P = new int[A.length+1][m+1];
for(int i = 1;i<= A.length; i++){
for(int j = m;j>=0;j--){
if(j>=A[i-1]){
P[i][j] = P[i-1][j-A[i-1]] + V[i-1];
}
P[i][j] = Math.max(P[i][j],P[i-1][j]);
}
}
return P[A.length][m];
}
