代码随想录Day35 | 01背包问题 二维,01背包问题 一维,416.分割等和子集

代码随想录Day35 | 01背包问题 二维,01背包问题 一维,416.分割等和子集

01背包问题 二维

动态规划经典问题

dp定义：

dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

状态转移方程：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

• dp[i - 1][j]表示不把物品i装入背包
• dp[i - 1][j - weight[i]] + value[i]表示把物品i装入背包，dp[i - 1][j - weight[i]]是背包去除物品i的重量后，可以得到的最大价值

初始化：

• 第一列，即背包容量为0时，肯定是0，数组初始化已经默认是0
• 状态转移方程要用到i - 1行，所以第一行必须初始化

遍历：

先遍历行，也就是先遍历物品，再遍历背包容量

import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        // n种物品,背包容量bagWeight
        int n = scanner.nextInt();
        int bagWeight = scanner.nextInt();
        
        int[] weight = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++)
            weight[i] = scanner.nextInt();
        for (int i = 0; i < n; i++)
            value[i] = scanner.nextInt();
            
        int[][] dp = new int[n][bagWeight + 1];
        
        for (int j = weight[0]; j <= bagWeight; j++) {
            dp[0][j] = value[0];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= bagWeight; j++) {
                if (j < weight[i])
                    dp[i][j] = dp[i - 1][j];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
        
        System.out.println(dp[n - 1][bagWeight]);
        return;
    }
}

01背包问题 一维

因为在二维里，dp[i][j]的值只与左上角（上一行且左边）的值有关，所以只保存一行的值即可。

状态转移方程：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

遍历顺序：

因为要用到左上角的值，在一维里就是左边的值，所以j要从后往前遍历，不然会影响到左边的值

import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        // n种物品,背包容量bagWeight
        int n = scanner.nextInt();
        int bagWeight = scanner.nextInt();
        
        int[] weight = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++)
            weight[i] = scanner.nextInt();
        for (int i = 0; i < n; i++)
            value[i] = scanner.nextInt();
            
        int[] dp = new int[bagWeight + 1];
        
        for (int j = weight[0]; j <= bagWeight; j++) {
            dp[j] = value[0];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        
        System.out.println(dp[bagWeight]);
        return;
    }
}

416.分割等和子集

难点在于将问题转换为动态规划问题：

• 视为背包问题，能否把容量为 sum/2 的背包刚好装满
• 物品的重量与价值相等

然后就是背包问题的代码形式

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length < 2) return false;
        // 视为背包问题，能否把容量为 sum/2 的背包刚好装满
        // 物品的重量与价值相等
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;
        
        int target = sum / 2;
        int[] dp = new int[target + 1];

        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                // 取当前数 或 不取当前数
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            // 每次判断是否装满
            if (dp[target] == target)
                return true;
        }

        return dp[target] == target;
    }
}

[j]: