Given n items with size Ai and value Vi, and a backpack with size m. What‘s the maximum value can you put into the backpack? Notice You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m. Have you met this question in a real interview? Yes Example Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9. Challenge O(n x m) memory is acceptable, can you do it in O(m) memory?
状态和状态方程的思路和1 一样, 当前背包加用vs 不用, 找到与题意链接的一个状态, 再找他的对立面
int[][] f = new int[A.length + 1][m + 1];
f[0][0] = 0;
//initialize
for (int i = 0; i <= A.length; i++) {
f[i][0] = 0;
}
for (int i = 1; i <= m; i++) {
f[0][i] = 0;
}
//function
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= A[i - 1]) {
f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return f[A.length][m];
}
一维
public int backPackII(int m, int[] A, int V[]) {
int[] dp = new int[m+1];
for (int i=0;i<A.length;i++)
{
for (int j=m;j>=A[i];j--)
{
dp[j] = Math.max(dp[j],dp[j-A[i]]+V[i]);
}
}
return dp[m];
}
原文：http://www.cnblogs.com/apanda009/p/7294173.html