算法训练营Day36

#Java #动态规划

开源学习资料

Feeling and experiences：

动态规划：01背包理论基础：卡码网题目链接

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。?

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

经典背包问题：

01 背包

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

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        //现根据题目写出输入
        
        Scanner sc = new Scanner(System.in);
        
        int M = sc.nextInt();
        int N = sc.nextInt();
        
        int[] values = new int[M];
        int[] weights = new int[M];
        
        //给数组赋值
        for(int i = 0;i < M;i++){
            weights[i] = sc.nextInt();
        }
        
        for(int i =0;i < M;i++){
            values[i] = sc.nextInt();
        }
        
        //创建dp数组
        int [][]dp = new int[M][N+1];
        
        //初始化dp数组
        for(int i = weights[0];i <= N;i++){
            dp[0][i] = values[0];
        }
        
        //遍历 递推
        for(int i = 1;i < M;i++){
            for(int j =0;j<=N;j++){
                if(weights[i] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i]);
                }
            }
        }
        System.out.println(dp[M-1][N]);
    }
}

notice：卡码网代码需要写输入代码。

初始化dp数组：

?这个循环初始化了dp数组的第一行，设定了只考虑第一个物品（索引为0）时的情况。

?如果第一个物品的重量（假设为10）小于等于背包的当前容量（i），则这个背包能够装下这个物品，因此dp[0][i]（考虑第一个物品且背包容量为i时的最大价值）被设置为该物品的价值values[0]。
对于不能装下第一个物品的情况（即i?<?weights[0]），dp[0][i]默认为0（Java中数组的初始值）。

递推公式：

? 外循环遍历物品（从第二个开始，因为第一个已经在初始化时考虑过了）。
? 内循环遍历所有可能的背包容量。
? 如果当前物品的重量大于背包的当前容量（weights[i]?>?j），那么这个物品无法被加入，因此最大价值与前一个物品时相同（即dp[i][j]?=?dp[i-1][j]）。
? 如果可以加入这个物品，我们需要决定是加入这个物品还是不加入。我们比较不加入这个物品时的最大价值（dp[i-1][j]）和加入这个物品后的总价值（dp[i-1][j-weights[i]]?+?values[i]）。
?

分割等和子集：力扣题目链接

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

示例 1：

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

抽象成背包问题，确实没有想到~

1. 初始检查:
? 检查数组长度是否小于2，如果是，直接返回false，因为无法分割成两个子集。
? 计算数组的总和sum和最大元素maxNum。

2. 总和的奇偶性检查:
? 如果sum是奇数，不能分割成两个和相等的子集，返回false。

3. 目标值设置:
? 将目标值设置为sum?/?2。如果能找到和为target的子集，另一个子集自然也是target。
4. 最大元素检查:

? 如果任何单个元素大于target，则无法分割，返回false。
5. 动态规划表dp初始化:
? 创建一个布尔类型的二维动态规划表dp。dp[i][j]表示考虑前i个数字时，是否存在一个子集的和为j。
? 初始化所有dp[i][0]为true，因为不选择任何数字时，子集和为0。
? 将dp[0][nums[0]]设置为true，表示考虑第一个数字时，能达到的和为nums[0]。

6. 动态规划计算:
? 对于每个元素num和每个目标和j，更新dp表。
? 如果j大于或等于当前数字num，则检查：
? 不包含当前数字（dp[i?-?1][j]）。
? 包含当前数字（dp[i?-?1][j?-?num]），意味着我们从j中减去当前数字的值，查看剩余值是否可以由前i-1个数字组成。
? 更新dp[i][j]为这两种情况的逻辑或（|）结果。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
}

Fighting！

?