Day39 代码随想录(1刷) 动态规划 0-1背包-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day39 代码随想录(1刷) 动态规划 0-1背包。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

46. 携带研究材料（第六期模拟笔试）

题目描述

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

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

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

状态：完成

思路：这是一个存粹的0-1背包的入门问题，先用二维的dp数组解决，dp[i][j]表示背包最大容量为j的时候从物品【0-i】任取，所以最后一个格就是背包容量是N时的最大价值，状态转移方程也是很好理解的dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i]),意思就是对比不取物品i时在这个容量时的最大价值和取这个物品在背包容量允许的情况下的价值。该题也是要初始化，dp[0][i]表示取物品0的最大价值。二维数组时先遍历物品还是背包容量都是可以的。

可以从上面的二维数组思路中看出状态转移的时候其实就是把dp[i-1]行的与dp[i-1][j-weights[i]]+values[i]进行对比所以我们可以直接用一个一维数组解决问题，这个数组中dp[i]表示背包容量为i的最大价值，转移方程与二维数组的基本一致就是dp[i]跟dp[i-weights[i]]+values[i]进行对比，但这里只能从大到小进行容量的遍历，因为如果小到大则会重复加了。

dp二维数组：

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        String l1=sc.nextLine();
        int M=Integer.valueOf(l1.split(" ")[0]),N=Integer.valueOf(l1.split(" ")[1]);
        int[] weights=new int[M];
        int[] values=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();
        }
        int[][] dp=new int[M][N+1];
        for(int i=0;i<=N;i++){
            if(weights[0]<=i)
            dp[0][i]=values[0];
        }
        for(int i=1;i<M;i++){
            for(int j=1;j<=N;j++){
                if(j-weights[i]<0) 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]);
        
    }
}

dp一维数组：

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        String l1=sc.nextLine();
        int M=Integer.valueOf(l1.split(" ")[0]),N=Integer.valueOf(l1.split(" ")[1]);
        int[] weights=new int[M];
        int[] values=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();
        }
        int[] dp=new int[N+1];
        for(int i=0;i<M;i++){
            for(int j=N;j>0;j--){
                if(j-weights[i]<0) break;
                dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);
            }
        }
        System.out.println(dp[N]);
        
    }
}

416. 分割等和子集

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

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：

1 <= nums.length <= 200

1 <= nums[i] <= 100

状态：没想出来

思路：这个是恰好相等类的问题，这里的物品质量跟物品价格都一致，我们使用一维dp数组去解决这个问题，dp[i]表示和为i时的最大数值，这题明显只有和为数组和的半时才能得到两个相等和的子数组。所以最后只要dp[target]==target表示存在这样的子数组。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int a:nums){
            sum+=a;
        }
        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>=0;j--){
                if(j-nums[i]<0) break;
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
}

文章来源地址https://www.toymoban.com/news/detail-856146.html

到了这里，关于Day39 代码随想录(1刷) 动态规划 0-1背包的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！