代码随想录打卡第四十四天|● 01 二维背包问题 ●一维背包问题-滚动数组 ● 416. 分割等和子集

什么是01背包

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

01背包的模板

二维dp数组

dp数组的含义

dp[i][j]含义下标为【0-i】之间的物品任取放进容量为j的背包里的最大价值

递推公式

dp[i][j]的值取决于放不放物品i
如果不放物品i：dp[i][j]为dp[i-1][j]
如果放物品i：dp[i-1][j-w[i]] 保证可以放入物品i（0-i-1的物品不放入i时的最大价值） dp[i][j] 为dp[i-1][j-w[i]]+v[i]
dp[i][j] 求两者最大值
递推公式：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i])

初始化

第一行和第一列均初始化

for (int j = 0 ; j < weight[0]; j++) { 
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5
6
7

遍历

有两个遍历维度：
物品和背包
两个遍历顺序：
正序遍历和倒序遍历
先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。

for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    	//如果整体的背包容量小于物品重量 dp[i][j] = dp[i - 1][j];
    	//前i-1个物品能放下的最大价值就是当前情况的最大价值
        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]);
    }
}
1
2
3
4
5
6
7
8

一维dp数组

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
我们发现可以把dp[i]的值覆盖到dp[i-1]上 这样可以实现一维数组
如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）

一维dp数组的动规五部曲分析

dp数组的含义
dp[j] 容量为j的背包的最大价值
递推公式
dp[j] =max(dp[j],dp[j-w[j]]+v[j])
dp[j] 表示不放物品j，即拷贝上一层
初始化
初始化 dp[0]=0;
非0下标初始化为0；
遍历顺序：

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

    }
}
1
2
3
4
5
6

为什么是倒序遍历？
正序遍历的话 会依托前面的dp[j] 正向遍历前面的dp[j]会被覆盖 之后再使用时 不是上一层的dp[j] 而是当前层新更新的dp[j] 这个dp[j]可能已经加入过物品i 这就导致i被重复添加
倒序遍历时 前面的dp[j]还没有被覆盖

    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] + " ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

416. 分割等和子集

题目链接：416. 分割等和子集
解题思路：数组的数字是物品，其重量和价值都是该数字。背包的容量是总和的一半。如果物品价值可以达到容量 则说明可以被分割
代码如下：

class Solution {
    public boolean canPartition(int[] nums) {
        //求背包容量
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }

        if(sum%2!=0){
            return false;
        }
        int capation = sum/2;
        int[] dp = new int[capation+1];
        for(int i=0;i<nums.length;i++) {
            for(int j=capation;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[capation]==capation){
            return true;
        }else{
            return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25