背包问题解析

1. 0-1背包

背包的能容纳的最大重量为W，有N个物品，每个物品的重量为w_i，价值为v_i。求背包可容纳的物品的最大价值。

定义二维数组dp[N][W]，dp[i][j]表示前i个物品在重量不超过j的情况下能容纳物品的最大价值。设第i件物品的重量为w_i, 价值为v_i，根据第i件物品是否在背包中，可以有两种情况：

第i件物品不放在背包中，dp[i][j]（前i件物品放入容量为j的背包的最大价值） = dp[i-1][j]（前i-1件物品放入容量为j的背包的最大价值）
第i件物品放入背包中，dp[i][j]（前i件物品放入容量为j的背包的最大价值） = dp[i-1][j-w_i] + v_i（前i-1件物品放入容量为j-w_i的背包的最大价值 + v_i）

dp[i][j]应该取两者的较大的，状态转移方程为：
$$
dp[i][j] = max{dp[i-1][j],\quad dp[i-1][j-w_i],+,v_i}
$$

public int solve(int[] weights, int[] values, int W, int N){
    
    int[][] dp = new int[N+1][W+1];
    
    for(int i = 1; i <= N; i++){
        int w = weights[i-1], v = values[i-1];
        for(int j = 1; j <= W; j++){
            dp[i][j] = dp[i-1][j];
            if(j - w >= 0){
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w] + v);
            }
        }
    }
    
    return dp[N][W];
}

空间优化

观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
$$
dp[j] = max{dp[j],,, dp[j-w_i],+,v_i}
$$
因为dp[j-w_i]代表的是dp[i-1][j-w_i]，为了避免覆盖掉dp[i-1][j-w_i]，也就是说要先计算 dp[i][j] 再计算 dp[i][j-w_i]，在程序实现时需要按倒序来循环求解。

public int solve(int[] weights, int[] values, int W, int N){
    
    int[] dp = new int[W+1];
    
    for(int i = 1; i <= N; i++){
        int w = weights[i-1], v = values[i-1];
        // dp[j] 代表没有第i件物品容量为j的最大价值
        for(int j = W; j >= w; j--){
            dp[j] = Math.max([j], dp[j-w] + v);
        }
    }
    
    return dp[N][W];
}

例题

416. 分割等和子集

我们可以先求出数组所有元素的和sum，问题可以转化为0-1背包问题：背包的容量为sum/2，原数组就是每件物品的重量，判断背包是否可以正好装满。

此问题没有涉及物品的价值：求的是是否能将背包装满，所以无需考虑物品的价值。

public boolean canPartition(int[] nums) {

    int n = nums.length;

    int sum = 0;
    for(int m : nums){
        sum += m;
    }
    if(sum % 2 == 1){
        return false;
    }

    int S = sum / 2;
    boolean[] dp = new boolean[S+1];
    dp[0] = true;

    for(int i = 1; i <= n; i++){    // 每个物品只用一次
        int weight = nums[i-1];
        for(int j = S; j >= weight; j--){    // 从后往前，先计算dp[j]，再计算dp[j-1]
            dp[j] = dp[j] || dp[j-weight];   // *****
        }
    }

    return dp[S];
}

494. 目标和

将数组按符号分为两个集和：带正号集和S1，带符号集和S2，可以得出：
$$
sum(S1) - sum(S2) = target\
sum(S1) + sum(S2) ,=, sum
$$
可以得出：
$$
2*sum(S1) = target + sum
$$
问题也可以转化为0-1背包问题：容量为(target+sum)/2，物品为数组，求有多少种方式可以将背包放满。

此问题求解的是背包放满有多少种方式，同样没有涉及到物品价值。

public int findTargetSumWays(int[] nums, int S) {

    int sum = 0;
    for(int m : nums){
        sum += m;
    }
    if((sum + S) % 2 == 1 || sum < S){   // 注意这里，否则会超出内存
        return 0;
    }

    int T = (sum + S) / 2;
    int[] dp = new int [T + 1];
    dp[0] = 1;
    int n = nums.length;

    for(int weight : nums){
        for(int j = T; j >= weight; j--){
            dp[j] += dp[j-weight];
        }
    }

    return dp[T];
}

这道题数组长度不会超过20，同样可以用DFS求解，时间复杂度O(2^n)。

474. 一和零

这道题如果仔细考虑一下，也是个0-1背包问题：背包的容量有两个限制m和n，物品就是字符串数组，每个物品的代价就是字符串中0和1的数量，求背包中最多能放如多少个物品。

public int findMaxForm(String[] strs, int m, int n) {

    int[][] dp = new int[m+1][n+1];    // 背包有两个限制属性

    for(String s : strs){    // 每个物品只能放一次
        int zero = 0, one = 0;    // 物品的两个属性代价
        for(char ch : s.toCharArray()){
            if(ch == '0'){
                zero++;
            }
            else{
                one++;
            }
        }

        for(int j = m; j >= zero; j--){    // 0
            for(int k = n; k >= one; k--){    // 1
                dp[j][k] = Math.max(dp[j][k], dp[j-zero][k-one] + 1);
            }
        }
    }

    return dp[m][n];

}

0-1背包的特点

N个物品，每个物品两个属性<w, v>
每个物品在背包中可以放0个或1个
求容量不超出下的最大价值

2. 完全背包

背包的能容纳的最大重量为W，有N个物品，每个物品的重量为w_i，价值为v_i。求背包可容纳的物品的最大价值。完全背包问题中，每个物品放入的数量是不受限制的。

dp[i][j]表示前i个物品<w_i, v_i>放入容量为j背包时的最大代价，根据第i个物品放入到背包的状况，可以得到状态转移方程：
$$
dp[i][j] = max{dp[i-1][j],, dp[i-1][j-w_i] + v_i,, dp[i-1][j-2w_i]+2v_i,….}
$$

public int solve(int[] weights, int[] values, int W, int N){
    
    int[][] dp = new int[N+1][W+1];
    
    for(int i = 1; i <= N; i++){    // 放入每个物品
        int w = weights[i-1], v = values[i-1];    // 物品的代价和价值
        for(int j = 1; j <= W; j++){    // 
            dp[i][j] = dp[i-1][j];     // 不放入第i个物品
            for(int k = 1; k*w <= j; k++){    // 放入1个，2个....
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*w] + k*v);
            }
        }
    }
    
    return dp[N][W];
}
空间压缩后
public int solve(int[] weights, int[] values, int W, int N){
    
    int[] dp = new int[W+1];
    
    for(int i = 1; i <= N; i++){    // 放入每个物品
        int w = weights[i-1], v = values[i-1];    // 物品的代价和价值
        for(int j = W; j >= 1; j--){    // 
            for(int k = 1; k*w <= j; k++){    // 放入1个，2个....
                dp[j] = Math.max(dp[j], dp[j-k*w] + k*v);
            }
        }
    }
    
    return dp[W];
}

另一种比较简洁的思路：

public int solve(int[] weights, int[] values, int W, int N){
    
    int[] dp = new int[W+1];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    
    for(int i = 1; i <= N; i++){    // 放入每个物品
        int w = weights[i-1], v = values[i-1];    // 物品的代价和价值
        for(int j = w; j <= W; j++){    // 
            if(dp[j-w] != -1){
                dp[j] = Math.max(dp[j], dp[j-w] + v);
            }
        }
    }
    
    return dp[W];
}

322. 零钱兑换

此问题是个完全背包问题：物品是硬币，可以无限次放入，背包容量是amount，求能将背包装满的组合数。

public int coinChange(int[] coins, int amount) {

       int[] dp = new int[amount+1];
       Arrays.fill(dp, -1);
       dp[0] = 0;

       for(int m : coins[i]){
           for(int j = m; j <= amount; j++){
               if(dp[j-m] != -1){
                   if(dp[j] == -1){
                       dp[j] = dp[j-m] + 1;
                   }
                   else{
                       dp[j] = Math.min(dp[j], dp[j-m]+1);
                   }
               }
           }
       }

       return dp[amount];
   }

518. 零钱兑换 II

完全背包，求组合数。

public int change(int amount, int[] coins) {

    int[] dp = new int[amount+1];
    dp[0] = 1;

    for(int coin : coins){
        for(int i = coin; i <= amount; i++){
            dp[i] += dp[i-coin];
        }
    }

    return dp[amount];

}

139. 单词拆分

这道题比较有意思，物品是单词字典，背包的容量是字符串长度，不过它的放入条件是字符串要相同。而且物品放入有先后顺序。带放入顺序的完全背包问题：

// 错误解法
public boolean wordBreak(String s, List<String> wordDict) {

        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        
        for(String str : wordDict){

            for(int i = str.length(); i <= len; i++){
                if(!dp[i] && dp[i-str.length()] && isSame(s, i-1, str)){
                    dp[i] = true;
                }
            }
        }

        return dp[len];
    }

// 正确解法
public boolean wordBreak(String s, List<String> wordDict) {

        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        
        for(int i = 1; i <= len; i++){
            for(String str : wordDict){
                int l = str.length();
                if(!dp[i] && i >= l && isSame(s, i-1, str)){
                    dp[i] |= dp[i-l];
                }
            }
        }

        return dp[len];
    }

    public boolean isSame(String str, int end, String s){
        int i = end, j = s.length()-1;
        while(i >= 0 && j >= 0){
            if(str.charAt(i) != s.charAt(j)){
                break;
            }
            i--;
            j--;
        }

        return j == -1;
    }

377. 组合总和 Ⅳ

求组合数，不同的序列被视为不同的组合，则需要考虑物品放入背包时的顺序：

public int combinationSum4(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] maximum = new int[target + 1];
    maximum[0] = 1;
    Arrays.sort(nums);
    for (int i = 1; i <= target; i++) {
        for (int j = 0; j < nums.length && nums[j] <= i; j++) {
            maximum[i] += maximum[i - nums[j]];
        }
    }
    return maximum[target];
}

无视组合数字的中的先后顺序的话：

public int combinationSum4(int[] nums, int target) {

    int[] dp = new int[target+1];
    dp[0] = 1;

    for(int m : nums){
        for(int j = m; j <= target; j++){
            dp[j] += dp[j-m];
        }
    }

    return dp[target];


}

完全背包的特点

N个物品，每个物品两个属性<w, v>
每个物品在背包中可以放0个或无限多个
求容量不超出下的最大价值

3. 多重背包

多重背包的特点

N个物品，每个物品两个属性<w, v>
每个物品都有一定的数量N_i，在背包中可以放入0-N_i
求容量不超出下的最大价值

4.多维费用背包

474. 一和零

属于0-1背包中的多维费用背包，答案见0-1背包。

多维费用背包的特点

N个物品，每个物品有多个限制属性如容量、体积，以及价值
放入看具体要求
求重量和体积都不超出下的最大价值