随想录日记part34
t i m e : time: time: 2024.04.02
主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及两个方面:
背包问题和分割等和子集。
- 01背包问题
- 416. 分割等和子集
动态规划五部曲:
【1】.确定dp数组以及下标的含义
【2】.确定递推公式
【3】.dp数组如何初始化
【4】.确定遍历顺序
【5】.举例推导dp数组
Topic101背包问题
题目:
小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。 小明的行李空间为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料只能选择一次,并且只有选与不选两种选择,不能进行切割。
输入描述:
第一行包含两个正整数,第一个整数 M 代表研究材料的种类,第二个正整数 N,代表小明的行李空间。
第二行包含 M 个正整数,代表每种研究材料的所占空间。
第三行包含 M 个正整数,代表每种研究材料的价值。
输入:
6
1
2
2
3
1
5
2
2
3
1
5
4
3
6\ 1\\ 2\ 2\ 3\ 1\ 5\ 2\\ 2\ 3\ 1\ 5\ 4\ 3
6 12 2 3 1 5 22 3 1 5 4 3
输出:
5
5
5
思路:
【1】.二维dp数组01背包
1.dp含义:dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
2.确定递推公式
有两个方向推出来dp[i][j]:
- 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
- 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值
所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);代码如下:
mport java.util.*;
class Main{
public static void main(String[] agrs){
Scanner sc = new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
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();
}
//dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少
int[][] dp=new int[m][n+1];
//初始化
for(int i=0;i<m;i++){
dp[i][0]=0;
}
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(j<weights[i])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]);
}
}
【2】.滚动数组01背包
倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。
为什么倒序遍历,就可以保证物品只放入一次呢?
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp数组已经都初始化为0)
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
代码如下:
import java.util.*;
class Main{
public static void main(String[] agrs){
Scanner sc = new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
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();
}
//dp[i]表示放进容量为j的背包,价值总和最大是多少
int[] dp=new int[n+1];
//初始化
//状态转换
for(int i=0;i<m;i++){
for(int j=n;j>=weights[i];j--){
dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);
}
}
System.out.println(dp[n]);
}
}
Topic2分割等和子集
题目:
给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
输入:
n
u
m
s
=
[
1
,
5
,
11
,
5
]
nums = [1,5,11,5]
nums=[1,5,11,5]
输出:
t
r
u
e
true
true
思路:
按照上面的五个步骤给出下面的代码,在注释中给出具体的思路:
递推我们理解一下:
整体代码如下:文章来源:https://www.toymoban.com/news/detail-846210.html
class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
//dp[j]表示背包总容量(所能装的总重量)是j,放进物品后,背的最大重量为dp[j]
int[] dp=new int[10001];
if(sum%2==1) return false;
sum=sum/2;
for(int i=0;i<nums.length;i++){
for(int j=sum;j>=nums[i];j--){
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
if(dp[sum]==sum) return true;
else return false;
}
}
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度:
O
(
n
)
O(n)
O(n)文章来源地址https://www.toymoban.com/news/detail-846210.html
到了这里,关于代码学习记录34---动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!