Backpack I 92

Question

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

Notice

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 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.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

Solution

基础背包类问题，用DP解。两种方法本质都一样，只是表述不同。

第一种方法为dp[i][j]表示i容量的背包在j件物品中能取的最大值。分两种情况：一种情况为不要第j件物品，则最优情况为背包容量为i时前j－1件物品的最优值；第二种情况为要第j件物品，则最优情况为背包容量为i-第j件物品体积时前j－1件物品的最优值加上第j件物品的值，这种情况要求i-第j件物品体积 >= 0。取两种情况里面较大的作为dp[i][j]的值。

第二种方法dp[i][j]表示前i件物品能否填满容量为j的背包。分两种情况：一种情况为不要第i件物品，则dp[i][j]=dp[i-1][j]；第二种情况为要第j件物品，则dp[i][j] = dp[i-1][j - A[j]],不过这种情况要求j - A[j]>0。取两种情况里面较大的作为dp[i][j]的值。

代码如下：

Solution 1:

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) {
        // write your code here
        if(m == 0 || A == null || A.length == 0){
            return 0;
        }

        int n = A.length;
        int[][] fillPack = new int[m + 1][n + 1];

        for(int i = 0; i <= m; i++){
            fillPack[i][0] = 0;
        }

        for(int j = 0; j <= n; j++){
            fillPack[0][j] = 0;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i - A[j - 1] >= 0){
                    //一种情况为不要第j件物品，则最优情况为背包容量为i时前j－1件物品的最优值；第二种情况为要第j件物品，则最优情况为背包容量为i-第j件物品体积时前j－1件物品的最优值加上第j件物品的值。
                    fillPack[i][j] = Math.max(fillPack[i][j - 1], fillPack[i - A[j - 1]][j - 1] + A[j - 1]);
                }else{
                    fillPack[i][j] = fillPack[i][j - 1];
                }
            }
        }

        return fillPack[m][n];
    }
}

Solution 2:

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 f[][] = new boolean[A.length + 1][m + 1];
        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = false;
            }
        }
        f[0][0] = true;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j <= m; j++) {
                f[i + 1][j] = f[i][j];
                if (j >= A[i] && f[i][j - A[i]]) {
                    f[i + 1][j] = true;
                }
            } // for j
        } // for i

        for (int i = m; i >= 0; i--) {
            if (f[A.length][i]) {
                return i;
            }
        }
        return 0;
    }
}