backpack(1)

0-1 背包
背包问题中的第一种模型,就是给定一个背包的容量V,以及一个有关物品的数组A[],每个物品要么不取,要么只能取一个。问题通常是最多可以装多满,是否可以装满等。

Description Given n items with size Ai, 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, 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.

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

分析:
(1) 贪心是不能得到最优解的, eg: m = 4, A[3] = {3, 2, 2};
(2) dfs枚举:对所有物品都尝试取或者不取,时间复杂度是O(2^n).
(3) 暴力枚举是指数级别的原因是在尝试第i项的时候把前面得工作又做了一遍,所以应该用dp.

定义dp(i, j): 当背包容量为j时,用前i种物品可以装的最大体积。
所以原问题就是要求dp(m, n);

Solution 1
状态转移方程:dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i])
第一项是用前(i - 1)种物品可以装的最大体积(也就是不用第i种物品),第二项是使用第i项物品的最大体积。

代码:

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
        int len = A.length;
        int[][] dp = new int[len + 1][m + 1];
        for(int i = 0; i <= len; i++) dp[i][0] = 0;
        for(int i = 1; i <= len; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= A[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
                }
            }
        }
        return dp[len][m];
    }
}

复杂度:
time: O(m * n)
space: O(m * n)

Solution 2(滚动数组)
定义dp(i): 在当前容量为i时可以装的最大体积;
状态转移方程: dp[i] = Math.max(dp[i], dp[i - A[j]] + A[j])

代码:

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
        int len = A.length;
        int[] dp = new int[m + 1];
        for(int i = 1; i <= len; i++) {
        //注意,这里需要倒序
            for(int j = m; j >= A[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + A[i - 1]);
            }
        }
        return dp[m]; 
    }
}

复杂度:
time: O(m * n)
space: O(m)

评论

暂无评论