算法训练营day36 | {1.01背包问题（二维）, 2.01背包问题（一维）, 416.分割等和子集}

第九章动态规划part03，正式开始背包问题。

1. 01背包问题（二维）

题目链接：46. 携带研究材料
文档讲解：代码随想录
视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法
状态：

1.1 理论基础

对于面试的话，掌握01背包和完全背包，就够用了，而完全背包又是01背包稍作变化而来，所以背包问题的理论基础重中之重是01背包。力扣上没有纯粹的01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。
几种背包问题

1.2 01背包

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

首先，暴力解法可以想到用回溯，穷举每件物品取或不取，搜索出所有情况，时间复杂度为O(2^n)，n为物品数量。

回溯算法三部曲：

参数和返回值是什么？ 参数包括weight数组、value数组、背包容量w、物品数量n，以及遍历的物品个数index，当前已放置的重量curWeight，已获得的价值curValue。
确定递归的终止条件。 让所有物品都遍历完之后，收割结果，终止本层递归。
确定单层搜索的过程。 原本是for循环用于横向遍历，但在01背包中一个节点只有两种状态，即不选当前物品，或选中当前物品；递归用于纵向遍历，注意和回溯配合使用。

剪枝优化：选中当前物品的前提是背包还能装，如果超过限制，则不继续递归。

▶

01背包-回溯暴力解法

public class Solution {
    int maxValue = 0;
    public int knapsack(int[] weight, int[] value, int w) {
        backtracking(weight, value, w, 0, 0, 0);
        return maxValue;
    }

    public void backtracking(int[] weight, int[] value, int w, int index, int curWeight, int curValue) {
        if (index == weight.length) {
            maxValue = Math.max(maxValue, curValue);
            return;
        }

        backtracking(weight, value, w, index + 1, curWeight, curValue);

        if (curWeight + weight[index] <= w) {
            backtracking(weight, value, w, index + 1,
                    curWeight + weight[index], curValue + value[index]);
        }
    }
}

下面举一个例子：背包最大重量为4。物品如下，问背包能背的物品最大价值是多少？

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

1.3 二维dp数组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数组如何初始化: dp[i][j]依赖于左上方和正上方，所以需要初始化第一行（假设列为物品，行为背包重量）；第一列，当背包最大重量为0时，自然的赋值为0；其他位置取值任意，不影响。
确定遍历顺序: 先遍历物品后遍历背包；或者先遍历背包后遍历物品均可以。
举例推导dp数组:

再次强调，当j < weight[i]，意味着第i个物品装不下，无论如何都不能被选，所有合法的方法都只能来自 0 ~ i-1 的物品。而dp[i-1][j]已经是在容量j下，前i-1个物品的最优，除非引入第i个物品。
DP的每一个状态，本质上都是在回答：在这个约束下，我还能做得比过去更好吗？

▶

01背包-dp二维数组

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();  // 物品数量
        int n = scanner.nextInt();  // 背包最大重量
        int[] weight = new int[m];
        int[] value = new int[m];
        for (int i = 0; i < m; i++) {
            weight[i] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            value[i] = scanner.nextInt();
        }

        System.out.println(Main.knapsack(weight, value, m, n));
    }

    public static int knapsack(int[] weight, int[] value, int m, int n) {
        int[][] dp = new int[m][n + 1];
        for (int j = 0; j <= n; j++) {
            if (weight[0] <= j) dp[0][j] = value[0];
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j >= weight[i])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[m - 1][n];
    }
}

2. 01背包问题（一维）

题目链接：46. 携带研究材料
文档讲解：代码随想录
视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！
状态：01背包的滚动数组，把二维dp降为一维。

2.1 一维dp数组01背包

对于背包问题状态都是可以压缩的。在使用二维数组的时候，递推公式如上，完全可以把dp[i - 1]那一层拷贝到dp[i]上，进一步，与其拷贝，不如只用一个一维数组dp[j]。

动规五部曲：

确定dp数组以及下标的含义: dp[j]的定义：在“只考虑前 i 个物品”的前提下，容量为j背包所背的最大价值。
确定递推公式: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
dp数组如何初始化: 背包容量为0时，dp[0]=0; 其他位置数字只要比物品最低价值小即可，保证会被覆盖。
确定遍历顺序: 只能先遍历物品，后遍历背包，并且背包是从后往前遍历的。
举例推导dp数组: 一维dp，分别用物品0，物品1，物品2来遍历背包，结果如下：

▶

01背包-dp一维数组

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();  // 物品数量
        int n = scanner.nextInt();  // 背包最大重量
        int[] weight = new int[m];
        int[] value = new int[m];
        for (int i = 0; i < m; i++) {
            weight[i] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            value[i] = scanner.nextInt();
        }

        System.out.println(Main.knapsack(weight, value, m, n));
    }

    public static int knapsack(int[] weight, int[] value, int m, int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = n; j >= 0; j--) {
                if (j >= weight[i])
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[n];
    }
}

关于为什么只能先遍历物品，其实很好理解，看一维dp数组dp[j]的语义，关键词只考虑前i个物品，外层是物品，状态转移才是合理有意义的。

416. 分割等和子集

题目链接：416.分割等和子集
文档讲解：代码随想录
视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集
状态：看到子集，想到可以用回溯暴力搜索，但是树太深了复杂度过高。或转化为0-1背包。

3.1 解题分析

问题转化：假设数组元素的总和为total，那么一半则为total/2（可以看出total为奇数时无解）。假设背包容量为total/2，数组元素相当于物品，元素值就是value，能否找到一种情况让这个背包价值最大并且刚好装满？若最后剩余容量为0，返回true。

动规五部曲：

确定dp数组以及下标的含义: dp[j]的定义：[0~i]的物品任意取，容量为j的背包所背的最大价值。
确定递推公式: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
dp数组如何初始化: 容量为0时 dp[0]=0
确定遍历顺序: 只能先遍历物品，保持dp数组语义，并倒序遍历背包容量防止覆盖。
举例推导dp数组: nums = [1,5,11,5]

3.2 解题小结

▶

416. 分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;
        int maxValue = knapsack(nums, nums.length, total / 2);
        if (maxValue != total / 2) return false;
        return true;
    }

    public int knapsack(int[] nums, int m, int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = n; j >= 0; j--) {
                if (j >= nums[i])
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[j] == n) return n;
            }
        }
        return dp[n];
    }
}