背包全集

摘要

背包问题是经典问题. 给一堆items, 每个items[i]有重量; 再给一个包. 分为几种问:

• 每个item只用一次, 最多能装多满(不能爆)? Backpack I
• 每个item只用一次, 最多多少种装满的办法? Backpack V
• 每个item可用无限次, 最多多少种装满的办法? Backpack VI

虽然问法很多, 但是万变不离其宗: "...你的背包/对我沉重的审判..."
关键点, 就是那个重量: weight.

背包问题都将围绕着item weight的状态来考虑, 永远不要忘记了考虑weight.

情况1: 每个item只用一次, 最多能装多满(不能爆)?

考虑: 用i个item (可跳过地取), 是否能装到weight w?
需要从'可能性'的角度考虑, 不要搞成单一的最大值问题.

1. 背包可装的物品大小和总承重有关.
2. 不要去找dp[i]前i个物品的最大总重, 找的不是这个.
   dp[i]及时找到可放的最大sum, 但是i+1可能有更好的值, 把dp[i+1]变得更大更合适.

boolean[][] dp[i][j]表示: 有前i个item, 用他们可否组成size为j的背包? true/false.
(反过来考虑了，不是想是否超过size j, 而是考虑是否能拼出exact size == j)
注意: 虽然dp里面一直存在i的位置, 实际上考虑的是在i位置的时候, 看前i-1个item.

多项式规律:

1. picked A[i-1]: 就是A[i-1]被用过, weight j 应该减去A[i-1]. 那么dp[i][j]就取决于dp[i-1][j-A[i-1]]的结果.
2. did not pick A[i-1]: 那就是说, 没用过A[i-1], 那么dp[i][j]就取决于上一行d[i-1][j]
   dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]]

结尾:
跑一遍dp 最下面一个row. 从末尾开始找, 最末尾的一个j (能让dp[i][j] == true)的, 就是最多能装的大小 :)

时间，空间都是：O(mn)

/*
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.

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

Note
You can not divide any item into small pieces.
*/
public class Solution {
    
    public int backPack(int m, int[] A) {
        if (A == null || A.length < 0) {
            return 0;
        }
        int n = A.length;
        boolean[][] dp = new boolean[n + 1][m + 1];
        
        // weight 0 is a valid value.
        // items does not have 0's item, so we need to init dp based for all entries where i == 0
        dp[0][0] = true;
        for (int j = 1; j <= m; j++) {
            dp[0][j] = false;
        }
        
        // Calculcate possibility for i items to fill up w weight
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // default: item(i-1) not used:
                dp[i][j] = dp[i - 1][j];
                if (j - A[i - 1] >= 0) { // possible to use item(i-1)
                    dp[i][j] |= dp[i - 1][j - A[i - 1]]; // use item(i-1)
                }
            }
        }
        
        // Find max weight size that makes dp[i][j] true
        for (int j = m; j >= 0; j--) {
            if (dp[n][j]) {
                return j;
            }
        }
        return 0;
    }
}

//空间优化: 滚动数组, 让空间dp[2][m+1] -> O(m)空间
public class Solution {
    
    public int backPack(int m, int[] A) {
        if (A == null || A.length < 0) {
            return 0;
        }
        int n = A.length;
        boolean[][] dp = new boolean[2][m + 1];
        int curr = 0;
        int pre = 1;
        // weight 0 is a valid value.
        // items does not have 0's item, so we need to init dp based for all entries where i == 0
        dp[curr][0] = true;
        for (int j = 1; j <= m; j++) {
            dp[curr][j] = false;
        }
        
        // Calculcate possibility for i items to fill up w weight
        for (int i = 1; i <= n; i++) {
            curr = pre;
            pre = 1 - curr;
            for (int j = 0; j <= m; j++) {
                // default: item(i-1) not used:
                dp[curr][j] = dp[pre][j];
                if (j - A[i - 1] >= 0) { // possible to use item(i-1)
                    dp[curr][j] |= dp[pre][j - A[i - 1]]; // use item(i-1)
                }
            }
        }
        
        // Find max weight size that makes dp[i][j] true
        for (int j = m; j >= 0; j--) {
            if (dp[curr][j]) {
                return j;
            }
        }
        return 0;
    }
}

情况2: 每个item只用一次, 最多能装多满(不能爆)?Backpack V

[委婉待续]

情况3: 每个item只用一次, 最多能装多满(不能爆)?Backpack VI

[委婉待续]