代码随想录算法训练营第三十五天 | 01背包问题(二维,一维) | 416. 分割等和子集 | 1049.最后一块石头的重量II

01背包问题 二维

代码随想录

视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

题目链接：46. 携带研究材料（第六期模拟笔试）

题目描述：

背包问题

实现思路：

背包问题动态规划思路，研究在背包的每一个容量值的情况下，与所有物品直接的关系

dp数组：dp[i][j] 容量 j 与物品 i 的关系

推导公式：比较是否应该拿取该物品。不拿: dp[i-1][j], 拿取dp[i-1][j-weight] + value。dp[i][j] = Max(dp[i-1][j], dp[i-1][j-weight] + value)

初始化：dp[i][j]依赖左侧单元格和上侧单元格，所以需要初始化第一行和第一列。第一行代表放置物品1，如果容量值能放得下第一个物品，就初始化为物品价值，否则为0。第一列为背包容量为0的情况，初始化为0.

遍历顺序：依赖左侧和上侧，满足从上到下和从左到右的遍历顺序即可。先左右再上下就是挨个遍历物品，判断这个物品是否要拿。先上下再左右，就是判断背包各个容量值时，应该拿取哪些物品。

代码实现：

import java.util.Scanner;

public class Main {
    public static void main (String[] args) throws CloneNotSupportedException{
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        
        int[] weight = new int[m];
        int[] value = new int[m];

        for (int i=0; i<m; i++) {
            weight[i] = in.nextInt();
        }
        for (int i=0; i<m; i++) {
            value[i] = in.nextInt();
        }

        int[][] dp = new int[m][n+1];
        for (int i=weight[0]; i<=n; i++) {
            dp[0][i] = value[0];
        }
        
        for (int i=1; i<m; i++) {
            for (int j=1; j<=n; 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[m-1][n]);
    }

}

01背包问题 一维

代码随想录

视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

题目链接：

题目描述：

实现思路：

使用一维数组代替二维数组。二维数组的每一行，是对上一行的覆盖，所以只需要一个一维数组保存数据即可。

每一个值

dp数组：dp[j] 当前物品在背包容量为j时的物品价值

推导公式：dp[j] = Max(dp[j], dp[j-weight] + value)

初始化：（第一行）先初始化为第一个物品的价值

遍历顺序：依次遍历物品，从右向左遍历背包，因为需要依赖原来的左边的值。

代码实现：

import java.util.Scanner;

public class Main {
    public static void main (String[] args) throws CloneNotSupportedException{
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        
        int[] weight = new int[m];
        for (int i=0; i<m; i++) {
            weight[i] = in.nextInt();
        }
        int[] value = new int[m];
        for (int i=0; i<m; i++) {
            value[i] = in.nextInt();
        }

        int[] dp = new int[n+1];
        for (int i=weight[0]; i<=n; i++) {
            dp[i] = value[0];
        }
        
        for (int i=1; i<m; i++) {
            for (int j=n; j>=weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
            }
        }
        
        System.out.println(dp[n]);
    }

}

416. 分割等和子集

本题是 01背包的应用类题目

代码随想录

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili

题目链接：416. 分割等和子集 - 力扣（LeetCode）

题目描述：

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

实现思路：

数组的和需要是偶数，才能得到子集的和。已知子集的和 target，那么判断能否从数组中挑选一些元素，使得其的和等于target。

选择一定数量的元素，凑成一个和。转换为背包问题就是，给你一个背包容量为 target 的背包，挑选物品装满背包。

为什么不能是背包价值 = target。因为背包问题中限制我们的是背包容量，我们需要尽力达到最大价值。

那么物品的weight和value怎么计算呢，放入一个元素，target就减少一点，所以元素的weight等于元素的值。更大的weight代表更多的value，所以元素的value也等于元素的值。

dp数组：dp[i][j] 代表背包容量为 j 的时候，有关物品 i 的最大值

推导公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)

初始化：初始化第一行为物品0的价值（如果放得进去）

遍历顺序：先左右，再上下（遍历每个物品在背包中的情况）

代码实现：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;

        int n = nums.length;
        int bagWeight = sum / 2;
        int[] weight = nums;
        int[] value = nums;

        int[][] dp = new int[n][bagWeight+1];
        for (int i=nums[0]; i<= bagWeight; i++)
            dp[0][i] = weight[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]);
            }
        }
        
        // 背包是否放满物品
        return dp[n-1][bagWeight] == bagWeight;
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        
        for (int i=0; i<nums.length; i++) {
            sum += nums[i];
        }

        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]);
            }
        }

        return dp[target] == target;
    }
}

1049.最后一块石头的重量II

代码随想录

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili

题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

题目描述：

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

实现思路：

拿出来两个石头 x，y，得到一个新石头重量为 y-x。希望计算出最小的可能重量。

如果所有的石头能够分成相等重量的子集，那么这两个子集里的石头互相与对方消耗，最终会得到0。

如果不能相消，总重量为 2x+1,那么我们期望一个子集的重量为 x, 另一个子集重量为 x+1，这样能得到最小值 1。

所以我们应该尽力寻找这么一个子集，子集里的石头重量等于总重量的一半，然后与另一个子集里的石头相消。

dp数组：dp[j] 当前物品对应背包容量的最大值

推导公式：dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);

初始化：第一行为第一个物品重量

遍历顺序：依次遍历物品，然后从右向左遍历背包

代码实现：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalWeight = Arrays.stream(stones).sum();
        int bagWeight =totalWeight >> 1;
        int n = stones.length;

        int[] dp = new int[bagWeight+1];
        for (int j=stones[0]; j<=bagWeight; j++)
            dp[j] = stones[0];
        
        for (int i=1; i<n; i++) {
            for (int j=bagWeight; j>=stones[i]; j--)
                dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
        }
        
        return totalWeight - 2*dp[bagWeight];
    }
}