动态规划解法：01 背包问题与分割等和子集

4. 填表顺序

同上，从上往下，从左往右。

5. 返回值

打印 dp[n][V] 即可。若是 -1 则输出 0。

空间优化

利用滚动数组做空间上的优化，将二维数组压缩为一维数组。

1. 删除所有的 i 维。
2. 填表时从右往左遍历 j。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = 1010;
        int n = in.nextInt();
        int V = in.nextInt();
        
        int[] v = new int[N];
        int[] w = new int[N];
        for (int i = 1; i <= n; ++i) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        // 1. 解决第一个问题：求这个背包至多能装多大价值的物品
        int[] dp1 = new int[N];
        for (int i = 1; i <= n; ++i) {
            for (int j = V; j >= v[i]; --j) {
                dp1[j] = Math.max(dp1[j], w[i] + dp1[j - v[i]]);
            }
        }
        System.out.println(dp1[V]);

        // 2. 解决第二个问题：若背包恰好装满，求至多能装多大价值的物品
        int[] dp2 = new int[N];
        for (int i = 1; i <= V; ++i) {
            dp2[i] = -1;
        }
        dp2[0] = 0;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = V; j >= v[i]; --j) {
                if (dp2[j - v[i]] != -1) {
                    dp2[j] = Math.max(dp2[j], w[i] + dp2[j - v[i]]);
                }
            }
        }
        System.out.println((dp2[V] == -1 ? 0 : dp2[V]));
    }
}

分割等和子集

题目描述

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]。

示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

动态规划解法

1. 预处理

直接去判断两个子集的元素和是否相等会有点复杂，可以转化为只研究一个子集等于原数组元素和的一半，即在数组中选择一些数，这些数的和是否等于原数组元素和的一半。

2. 状态表示

dp[i][j] 表示在 nums 的前 i 个位置中选择一些数，所有选法中，是否存在一些数，使得这些数之和为 j。

3. 状态转移方程

根据最后一个位置 nums[i] 是否选择来划分情况：

1. nums[i] 不选：dp[i][j] = dp[i-1][j]
2. nums[i] 要选：需要保证所选数之和不超过 j，即 j - nums[i] >= 0，则 dp[i][j] = dp[i-1][j - nums[i]] 综合为：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]

4. 初始化

dp 表多创建一行一列，需要处理两个问题：

• 第一行 i=0 意味着没有元素可选，怎么选最大值都只能是 false，所以 dp[0][0] = true，其余全部初始化为 false。
• 第一列 j=0 意味着需要凑成和为 0，直接不选即可。故从 i=1 开始全部初始化为 true。

5. 填表顺序

根据状态转移方程可知，要想求得 dp[i][j] 就得先知道 dp[i-1][j] 和 dp[i-1][j-nums[i]]，所以可知填表顺序为：从上往下填写每一行，每一行从左往右填写。

6. 返回值

返回 dp[nums.length][原数组元素和的一半]。

空间优化

利用滚动数组做空间上的优化，将二维数组压缩为一维数组。

1. 删除所有的 i 维。
2. 填表时从右往左遍历 j。

代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int x : nums) sum += x;
        
        if (sum % 2 == 1) return false;
        int aim = sum / 2;
        
        boolean[] dp = new boolean[aim + 1];
        dp[0] = true;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = aim; j >= nums[i - 1]; --j) {
                if (!dp[j]) {
                    dp[j] = dp[j - nums[i - 1]];
                }
            }
        }
        return dp[aim];
    }
}