Backpack II 125

Question

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.

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?

Solution

和I类似。 value[i][j]表示容量为i的背包在前j件物品中能取的最大价值。分两种情况考虑：不要第j件物品，则value[i][j] = value[i][j-1]；要第j件物品，则value[i][j]=value[i－A［j］][j-1]+V[j]，这种情况要求i-A[j]>=0。取两种情况里面较大的作为value[i][j]的值。这种方法空间复杂度为O(n * m)。

第二种方法可以将空间复杂度优化到O(m)。f[j]表示背包容量为j时在前i件物品中能够选取的最大价值。到第i件物品时，考虑第i件物品装还是不装。背包容量j从最大的容量m开始依次递减遍历，只考虑更新背包容量大于A[i]的情况，即加上V[i]之后是否结果会更优，背包容量小于A[i]的情况不用考虑因为第i件物品根本装不进此时容量的背包。若结果更优，则更新此时的f[j]（即装第i件物品时情况更优），否则不变（即不装第i件物品时情况更优）。因为f会记录i之前所有的最优情况，因此只需要m空间即可。物品从0遍历到n－1，即可求出前n件物品的最优值。

其实第二种方法相当于使用滚动数组。因为状态函数为

value[i][j]=max(value[i－A［j］][j-1]+V[j], value[i][j-1])

可以看出只和j－1有关，因此保存两行信息就足够了。使用滚动数组必须逐行填写，因为在计算下一行的时候需要上一行的信息，像第一种方法中那样逐列填写就不行。

代码如下：

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

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

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i -A[j - 1] >= 0){
                    value[i][j] = Math.max(value[i][j - 1], value[i - A[j - 1]][j - 1] + V[j - 1]);
                }else{
                    value[i][j] = value[i][j - 1];
                }
            }
        }

        return value[m][n];
    }
}

space O(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[]) {
        // write your code here
        int[] f = new int[m + 1];

        for(int i = 0; i < n; i++){
            for(int j = m; j >= A[i]; j--){
                if(f[j] < f[j - A[i]] + V[i]){
                    f[j] = f[j - A[i]] + V[i];
                }
            }
        }

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

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

        for(int j = 1; j <= n; j++){
            for(int i = 1; i <= m; i++){
                if(i -A[j - 1] >= 0){
                    value[i][j % 2] = Math.max(value[i][(j - 1) % 2], value[i - A[j - 1]][(j - 1) % 2] + V[j - 1]);
                }else{
                    value[i][j % 2] = value[i][(j - 1) % 2];
                }
            }
        }
    }
}