Backpack I & II

Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack? 

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

n个整数a[1..n]，装m的背包

• state: f[i][j] “前i”个数，取出一些能否组成和为j
• function: f[i][j] = 如果不取最后第i个数f[i-1][j]  or 如果考虑第i个数 那么首先A[i] < j 成立的话 f[i-1][j - a[i]]

• intialize: f[X][0] = true; f[0][1..m] = false
• answer: 能够使得f[n][X]最大的X(0<=X<=m)

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        boolean [][] dp = new boolean[A.length + 1][m+1];
        for (int j = 0; j <= m; j++) {
            dp[0][j] = false;
        }
        for (int i = 0; i <= A.length; i++) {
            dp[i][0] = true;
        }
        for (int i =1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];//不取第i个数
                if (j >= A[i-1] && dp[i-1][j - A[i-1]]) {//取第i个数 A[i-1]表示第i个数
                    dp[i][j] = true;
                }
            }
        }
        for (int k = m; k >=0; k--) {
            if (dp[A.length][k]) {
                return k;
            }
        }
        return 0;
    }
}

Given n items with size A[i] and value V[i], and a backpack with size m. What's the maximum value can you put into the backpack?

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.

• state: f[i][j] “前i”个数，放入大小为j的背包获得的最大value
• function: f[i][j] = max{f[i-1][j],f[i-1][j-c[i]]+v[i]}         
• “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为f[i-1][j]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-c[i]的背包中”，此时能获得的最大价值就是f[i-1][j-c[i]]再加上通过放入第i件物品获得的价值V[i]。

• intialize: f[X][0] = 0; f[0][1..m] = 0
• answer: f[A.length][m]

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        int[][] dp = new int[A.length + 1][m + 1];
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 0;
        }
        for (int i = 0; i <= A.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (A[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }
            }
        }
        return dp[A.length][m];
    }
}