算法训练营Day36

2024-01-08 19:09:55

#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!


?

文章来源:https://blog.csdn.net/momolinshaomo/article/details/135458700
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。