✅背包理论根底 – 基于二维数组完成

01背包在背包问题中是根底的重中之重！

思路

说实话，背包问题深层的算法关于小白来说确实不太友好，看起来仍是有点费力的。
关于面试的话，其实掌握01背包，和彻底背包，就够用了，最多能够再来一个多重背包。
假如这几种背包，分不清，这儿有一个图，如下：

01 背包是啥

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

问背包能背的物品最大价值是多少？
以下解说和图示中呈现的数字都是以这个比如为例。

二维dp数组01背包

仍然动规五部曲剖析一波。

1. 确认dp数组以及下标的意义

关于背包问题，有一种写法， 是运用二维数组，即dp[i][j] 表明鄙人标为[0-i]的物品中取，放进容量为j的背包的最大价值总和。
只看这个二维数组的界说，咱们一定会有点懵，看下面这个图：

2. 确认递推公式

再回顾一下dp[i][j]的意义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么能够有两个方向推出来dp[i][j]，

• 不放物品i：由dp[i – 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此刻dp[i][j]便是dp[i – 1][j]。(其实便是当物品i的分量大于背包j的分量时，物品i无法放进背包中，所以背包内的价值仍然和前面相同。)
• 放物品i：那么容量就要相减减少，变成j – weight[i]。那么价值便是承接上一层dp[i – 1]再加上第 i 个物品价值，即dp[i – 1][j – weight[i]] + value[i] （物品i的价值），便是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]);

3. dp数组怎么初始化

关于初始化，一定要和dp数组的界说符合，不然到递推公式的时分就会越来越乱。
首要从dp[i][j]的界说动身，假如背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：

• 当 j < weight[0]的时分，dp[0][j] 应该是 0，因为背包容量比编号0的物品分量还小。
• 当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放满足放编号0物品。

代码初始化如下：

// i为0时,j不行weight[0]的设为0
for (int j = 0 ; j < weight[0]; j++) {  
// 当然这一步，假如把dp数组预先初始化为0了，这一步就能够省掉，但许多同学应该没有想清楚这一点隐含逻辑。
    dp[0][j] = 0;
}
// 正序遍历 - 下标从weight[0]开端,装上value[0](j够分量)
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

此刻dp数组初始化状况如图所示：

// 创立dp数组
int goods = weight.length;  // 获取物品的数量
int[][] dp = new int[goods][bagSize + 1];
// 初始化dp数组
// 创立数组后，其中默许的值便是0,因而j不行的状况不用初始化
for (int j = weight[0]; j <= bagSize; j++) {
    dp[0][j] = value[0];
}

4. 确认遍历次第

在如下图中，能够看出，有两个遍历的维度：物品与背包分量

// 填充dp数组
for (int i = 1; i < weight.length; i++) {
    for (int j = 1; j <= bagSize; j++) {
        if (j < weight[i]) {
            // j不行第i个大 - 不放
            dp[i][j] = dp[i-1][j];
        } else {
            // j满足第i个大 - 1. 不放 2. 放(可能会要丢到之前一些东西)
            dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
        }
    }
}

先遍历背包，再遍历物品，也是能够的！只需求将两个for循环上下移动（留意我这儿运用的二维dp数组）
例如这样：从上到下后从左到右

// weight数组的巨细 便是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

为什么也是能够的呢？
要了解递归的本质和递推的方向。
dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]); 递归公式中能够看出dp[i][j]是靠dp[i-1][j]和dp[i – 1][j – weight[i]]推导出来的。
dp[i-1][j]和dp[i – 1][j – weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的进程如图所示：

5. 举例推导dp数组

来看一下对应的dp数组的数值，如图：

终究结果便是dp[2][4]。
建议咱们此刻自己在纸上推导一遍，看看dp数组里每一个数值是不是这样的。
做动态规划的标题，最好的进程便是自己在纸上举一个比如把对应的dp数组的数值推导一下，然后在着手写代码！

✍手写剖析

全体代码如下:

public class BagProblem {
    public static void main(String[] args) {
        // 补充必要信息
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }
    /**
* 动态规划获得结果
* @param weight  物品的分量
* @param value   物品的价值
* @param bagSize 背包的容量
*/
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        // 创立dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];
        // 初始化dp数组
        // 创立数组后，其中默许的值便是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }
        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    // j不行第i个大 - 不放
                    dp[i][j] = dp[i-1][j];
                } else {
                    // j满足第i个大 - 1. 不放 2. 放(可能会要丢到之前一些东西)
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }
        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

总结

其实能够发现最简略的是推导公式了，推导公式估计看一遍就记下来了，但难就难在怎么初始化和遍历次第上。
可能有的同学并没有留意到初始化 和 遍历次第的重要性，后边继续刷力扣上背包面试标题的时分，就会有感受了

✅背包理论根底 – 根底一维数组完成

思路

把二维dp降为一维dp，用如下这个比如来进行解说
背包最大分量为4。
物品为：

问背包能背的物品最大价值是多少？

一维dp数组（翻滚数组）

关于背包问题其实状况都是能够压缩的。
在运用二维数组的时分，递推公式：dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]);
与 62 不同途径 – 空间优化 思维相似，当时这一层只用到上一层的值以服务下一层，到了下一层上上一层的数据就没用了。因而能够运用一维数组优化空间
动规五部曲剖析十分相似，如下：

1. 确认dp数组的界说

在一维dp数组中，dp[j]表明：容量为j的背包，所背的物品价值能够最大为dp[j]。

2. 一维dp数组的递推公式

dp[j]为 容量为j的背包所背的最大价值，那么怎么推导dp[j]呢？
dp[j]能够经过dp[j – weight[i]]推导出来，dp[j – weight[i]]表明容量为j – weight[i]的背包所背的最大价值。
dp[j – weight[i]] + value[i] 表明 容量为 j – 物品i分量 的背包 加上 物品i的价值。（也便是容量为j的背包，放入物品i了之后的价值即：dp[j]）
此刻dp[j]有两个选择，

• 一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，
• 一个是取dp[j – weight[i]] + value[i]，即放物品i，

指定是取最大的，毕竟是求最大价值，
所以递归公式为：

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

能够看出相关于二维dp数组的写法，便是把dp[i][j]中i的维度去掉了。

3. 一维dp数组怎么初始化

关于初始化，一定要和dp数组的界说符合，不然到递推公式的时分就会越来越乱。
dp[j]表明：容量为j的背包，所背的物品价值能够最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值便是0。
那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？
看一下递归公式：dp[j] = max(dp[j], dp[j – weight[i]] + value[i]);
dp数组在推导的时分一定是取价值最大的数，这要看标题给的价值，假如都是正整数那么非0下标都初始化为0就能够了。
这样才能让dp数组在递归公式的进程中取的最大的价值，而不是被初始值掩盖了。
（那么假设物品价值都是大于0的，所以dp数组初始化的时分，都初始为0就能够了。）

4. 一维dp数组遍历次第

代码如下：从右到左后从上到下

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

这儿咱们发现和二维dp的写法中，遍历背包的次第是不一样的！
二维dp遍历的时分，背包容量是从小到大，而一维dp遍历的时分，背包是从大到小。
为什么呢？
倒序遍历是为了确保物品i只被放入一次！。但假如一旦正序遍历了，那么物品0就会被重复加入屡次！
举一个比如：物品0的分量weight[0] = 1，价值value[0] = 15
假如正序遍历
dp[1] = dp[1 – weight[0]] + value[0] = 15
dp[2] = dp[2 – weight[0]] + value[0] = 30
此刻dp[2]就现已是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就能够确保物品只放入一次呢？
倒序便是先算dp[2]
dp[2] = dp[2 – weight[0]] + value[0] = 15 （dp数组现已都初始化为0）
dp[1] = dp[1 – weight[0]] + value[0] = 15
因为递推公式原理是依据左面的值得出，所以从后往前循环，每次获得状况不会和之前获得状况重合，这样每种物品就只取一次了。

那么问题又来了，为什么二维dp数组历的时分不用倒序呢？(j第一层循环 i第二层循环)
因为关于二维dp，dp[i][j]都是经过上一层即dp[i – 1][j]计算而来，本层的dp[i][j]并不会被掩盖！
（怎么这儿读不明白，咱们就要着手试一试了，空想仍是不靠谱的，实践出真知！）
再来看看两个嵌套for循环的次第，代码中是先遍历物品嵌套遍历背包容量，那可不能够先遍历背包容量嵌套遍历物品呢？
不能够！这样遍历次第变成从上到下后从右到左了，而从第二个值开端，所依靠的值并没有初始化，因而不能递推。
从本质上来讲，它仍是一个对二维数组的遍历，并且右下角的值依靠上一层左上角的值，因而需求确保左面的值仍然是上一层的，从右向左掩盖。
（这儿假如读不明白，就再回想一下dp[j]的界说，或许就把两个for循环次第颠倒一下试试！）
所以一维dp数组的背包在遍历次第上和二维其实是有很大差异的！，这一点咱们一定要留意。

5. 举例推导dp数组

一维dp，分别用物品0，物品1，物品2 来遍历背包，终究得到结果如下：

✍手写剖析

能够在纸上按着动规五部曲一步一步剖析，会有额定收获~：

public static void main(String[] args) {
    // 补充必要信息
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWight = 4;
    testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
    int wLen = weight.length;
    //界说dp数组：dp[j]表明背包容量为j时，能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    //遍历次第：先遍历物品，再遍历背包容量 - 从右往左后从上到下
    for (int i = 0; i < wLen; i++){
        for (int j = bagWeight; j >= weight[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    //打印dp数组
    for (int j = 0; j <= bagWeight; j++){
        System.out.print(dp[j] + " ");
    }
}

能够看出，一维dp 的01背包，要比二维简练的多！ 初始化 和 遍历次第相对简略了。
运用一维dp数组的写法，比较直观简练，并且空间复杂度还降了一个数量级！但需求在掌握其原理后写起来才顺利~

总结

假如是面试，可能会考一考纯背包问题（便是本文中的标题）
要求先完成一个纯二维的01背包，假如写出来了，然后再问为什么两个for循环的嵌套次第这么写？反过来写行不行？再讲一讲初始化的逻辑。
进而再要求完成一个一维数组的01背包，最终再问，一维数组的01背包，两个for循环的次第反过来写行不行？为什么？
（当然这些问题彻底能够运用费曼学习法，当成别人会提问你的问题，你怎么经过你的了解把他说出来~）
相信咱们应该对以上问题都有了答案！
力扣上的题都是背包问题的实际运用问题，根底离不开以上二维与一维数组的完成~

416 分割等和子集

思路

这道标题是要找是否能够将这个数组分割成两个子集，使得两个子集的元素和持平。
那么只要找到两个子集之和持平，sum = 子集之和 * 2。因而 sum / 2便是目标子集之和。

01背包问题

背包问题，有N件物品和一个最多能背分量为W 的背包。第i件物品的分量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
背包问题有多种背包方法，常见的有：01背包、彻底背包、多重背包、分组背包和混合背包等等。
要留意标题描绘中产品是不是能够重复放入。
即一个产品假如能够重复屡次放入是彻底背包，而只能放入一次是01背包，写法仍是不一样的。
要清晰本题中咱们要运用的是01背包，因为元素咱们只能用一次。
回归主题：首要，本题要求调集里能否呈现总和为 sum / 2 的子集。
那么来一一对应一下本题，看看背包问题怎么来解决。
只要确认了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2 – 看能否把背包塞满
• 背包要放入的产品（调集里的元素）分量为 元素的数值，价值也为元素的数值
• 背包假如正好装满，阐明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不行重复放入。

以上剖析完，咱们就能够套用01背包，来解决这个问题了。
动规五部曲剖析如下：

1. 确认dp数组以及下标的意义

01背包中，dp[j] 表明： 容量为j的背包，所背的物品价值最大能够为dp[j]。
本题中每一个元素的数值既是分量，也是价值。
套到本题，dp[j]表明 背包总容量（所能装的总分量）是j，放进物品后，背的最大分量为dp[j]。
那么假如背包容量为target， dp[target]便是装满 背包之后的分量，所以 当 dp[target] == target 的时分，背包就装满了,且满足题意。

2. 确认递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j – weight[i]] + value[i]);
本题，相当于背包里放入数值，那么物品i的分量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j – nums[i]] + nums[i]);

3. dp数组怎么初始化

在01背包，一维dp怎么初始化，现已讲过，
从dp[j]的界说来看，首要dp[0]一定是0。
假如标题给的价值都是正整数那么非0下标都初始化为0就能够了，假如标题给的价值有负数，因为递推需求取最大值，所以非0下标就要初始化为负无穷。
这样才能让dp数组在递推的进程中获得最大的价值，而不是被初始值掩盖了。
本题标题中 只包括正整数的非空数组，所以非0下标的元素初始化为0就能够了。
代码如下：

int target = sum / 2;
int[] dp = new int[target + 1];

4. 确认遍历次第

假如运用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！即为**从右到左从上到下。（**另外，本题求等和从后边遍历对现已从小到大排序的数组效率更快，如示例【1 5 5 11】当然了，正常来说都是随机的）
代码如下：

// 开端 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不行重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}

5. 举例推导dp数组

dp[j]的数值一定是小于等于j的。
假如dp[j] == j 阐明，调集中的子集总和正好能够凑成总和j，了解这一点很重要。
用例1，输入[1,5,11,5] 为例，如图：

public boolean canPartition(int[] nums) {
    // 默许一切数加起来等于最大的数sum = max * 2
    // 判空
    if (nums == null || nums.length == 0) return false;
    // 求和 - 判别是否是奇数 - false
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) return false;
    // 初始化
    int len = nums.length;
    int target = sum / 2;
    int[] dp = new int[target + 1];
    for (int i = 0; i < len; 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;
}

• 时刻复杂度：O(n^2)
• 空间复杂度：O(n)，尽管dp数组巨细为一个常数，可是大常数

总结

这道标题便是一道01背包运用类的标题，需求咱们拆解标题，然后套入01背包的场景。
01背包相关于本题，主要要了解，标题中物品是nums[i]，分量是nums[i]，价值也是nums[i]，背包体积是sum/2。
看代码的话，就能够发现，根本便是依照01背包的写法来的。

学习资料：

01背包问题 二维

01背包问题 一维

416. 分割等和子集