做周边的网站,医院建网站,好的办公室设计,企业网站建设的几种形式前言
这里记录一下陈菜菜的刷题记录#xff0c;主要应对25秋招、春招 个人背景 211CS本CUHK计算机相关硕#xff0c;一年车企软件开发经验 代码能力#xff1a;有待提高 常用语言#xff1a;C
系列文章目录
第九章 动态规划part03 文章目录 前言系列文章目录第九章 动态…前言
这里记录一下陈菜菜的刷题记录主要应对25秋招、春招 个人背景 211CS本CUHK计算机相关硕一年车企软件开发经验 代码能力有待提高 常用语言C
系列文章目录
第九章 动态规划part03 文章目录 前言系列文章目录第九章 动态规划part03 一、今日任务二、详细布置背包问题详解二维数组版本dp数组定义dp递推公式dp数组初始化确定遍历顺序 一维数组版本确定dp数组的定义一维dp数组的递推公式一维dp数组遍历顺序初始化 46. 携带研究材料提示样例1思路实战一维数组求解法 416. 分割等和子集提示样例1样例2思路实战 总结 一、今日任务
● 01背包问题 二维 ● 01背包问题 一维 ● 416. 分割等和子集
二、详细布置
背包问题详解 完全背包又是也是01背包稍作变化而来即完全背包的物品数量是无限的
二维数组版本
dp数组定义
dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。(i 来表示物品、j表示背包容量)
dp递推公式
-不放物品i背包容量为j里面不放物品i的最大价值是dp[i - 1][j]。 -放物品i背包空出物品i的容量后背包容量为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]);
dp数组初始化
首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。 在看其他情况。
状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。
dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。
那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。
当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。
for (int j 0 ; j weight[0]; j) { // 当然这一步如果把dp数组预先初始化为0了这一步就可以省略但很多同学应该没有想清楚这一点。dp[0][j] 0;
}
// 正序遍历
for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];
}最后初始化代码如下
// 初始化 dp
vectorvectorint dp(weight.size(), vectorint(bagweight 1, 0));
for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];
}确定遍历顺序
先遍历物品更好理解
// weight数组的大小 就是物品个数
for(int i 1; i weight.size(); i) { // 遍历物品for(int j 0; j bagweight; j) { // 遍历背包容量if (j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}
}一维数组版本
确定dp数组的定义
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]
一维dp数组的递推公式
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
一维dp数组遍历顺序
for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
}注意:这里和二维dp的写法中遍历背包的顺序是不一样的
二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。 倒序遍历是为了保证物品i只被放入一次 代码中是先遍历物品嵌套遍历背包容量那可不可以先遍历背包容量嵌套遍历物品呢
不可以
初始化
dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。
46. 携带研究材料 题目链接卡码网46 文章讲解代码随想录 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。
输入 第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。
第二行包含 M 个正整数代表每种研究材料的所占空间。
第三行包含 M 个正整数代表每种研究材料的价值。
输出 输出一个整数代表小明能够携带的研究材料的最大价值
提示
数据范围 1 N 5000 1 M 5000 研究材料占用空间和价值都小于等于 1000
样例1
输入
1 6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出
5
解释
小明能够携带 6 种研究材料但是行李空间只有 1而占用空间为 1 的研究材料价值为 5所以最终答案输出 5。 思路
这题就是0-1背包问题的经典应用。
实战 #include bits/stdc.h
using namespace std;
int main(){int M,N;cinMN;vectorint weight(M,0);vectorint value(M,0);vectorvectorint dp(M,vectorint(N1,0));int i,j;for(i0;iM;i){cinweight[i];}for(j0;jM;j){cinvalue[j];}for(jweight[0];jN;j){dp[0][j]value[0];}for(i1;iM;i){for(j0;jN;j){if(jweight[i])dp[i][j]dp[i-1][j];elsedp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]);}}coutdp[M-1][N]endl;return 0;
}
一维数组求解法
#include bits/stdc.h
using namespace std;
int main(){int n,bagweight;cinnbagweight;vectorint weight(n,0);vectorint value(n,0);int i,j;for(i0;in;i)cinweight[i];for(j0;jn;j)cinvalue[j];vectorint dp(bagweight1,0);for(i0;in;i){for(jbagweight;jweight[i];j--){dp[j]max(dp[j],dp[j-weight[i]]value[i]);}}coutdp[bagweight]endl;return 0;
}
416. 分割等和子集 题目链接LeetCode426 文章讲解图文讲解 题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
提示
1 nums.length 200 1 nums[i] 100
样例1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 样例2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。思路
0-1背包的变形。
实战
class Solution {
public:bool canPartition(vectorint nums) {int sum0;for(auto num:nums){sumnum;}if(sum%2!0)return false;int nnums.size(),bagweightsum/2;vectorint dp(bagweight1,0);int i,j;for(i0;in;i){for(jbagweight;jnums[i];j--){dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}if(dp[bagweight]bagweight)return true;return false;}
};总结
今天主要学习了0-1背包问题老师讲的很详细理解起来不难。后面还需要多做题巩固一下代码。 加油坚持打卡的第39天。
