当前位置: 首页 > news >正文

【中等】保研/考研408机试-动态规划1(01背包、完全背包、多重背包)

背包问题基本上都是模板题,重点:弄熟多重背包模板

dp[j]=max(dp[j-v[i]]+w[i],dp[j])    //核心思路代码(一维数组版)

dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])//二维数字版

一、 0-1背包

一般输入两个变量:体积(亦或者是重量)v和价值w

初始化好像不是必须的,如果出bug自己又搞不懂是哪里再加上吧

[NOIP2005]采药  登录—专业IT笔试面试备考平台_牛客网

#include <iostream>
#include <vector>
using namespace std;
int dp[1000];
int p[101];
int t[101];
int main() {int v,n;cin>>v>>n;for(int i=0;i<101;i++){p[i]=0;t[i]=0;}for(int i=0;i<100;i++){dp[i]=0;}for(int i=0;i<n;i++){cin>>t[i]>>p[i];}for(int i=0;i<n;i++){for(int j=v;j>=t[i];j--){   //注意是大于等于,有等于!这里错过好几次dp[j]=max(dp[j],dp[j-t[i]]+p[i]);}}cout<<dp[v];
}

 P1507 NASA的食物计划NASA的食物计划 - 洛谷

来个二维数组版的例子。

#include <iostream>
#include <vector>
using namespace std;
int dp[500][500];
int h1[401];
int t1[401];
int k1[501];
int main() {int h,t,n;cin>>h>>t>>n;//初始化 for(int i=0;i<400;i++){h1[i]=0;t1[i]=0;}for(int i=0;i<500;i++){k1[i]=0;}for(int i=0;i<n;i++){cin>>h1[i]>>t1[i]>>k1[i];}for(int i=0;i<n;i++){for(int j=h;j>=h1[i];j--){for(int k=t;k>=t1[i] ;k--){dp[j][k]=max(dp[j][k],dp[j-h1[i]][k-t1[i]]+k1[i]);}}}cout<<dp[h][t];   
}

二、 完全背包

一般输入两个变量:体积(亦或者是重量)v和价值w

完全背包的意思就是每个物品可以取无限次,0-1背包是每个物品只能取走一次。

完全背包例题:3. 完全背包问题 - AcWing题库

#include <iostream>
#include <vector>
#include<bits/stdc++.h> 
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int main() {int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>v1[i]>>w[i];}for(int i=0;i<n;i++){for(int j=v1[i];j<=v;j++){  //差别在这里dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);}}cout<<dp[v];
}

注意:可以看出,0-1背包和完全背包的问题的解决方案差别不大,主要就是在for(int j=v……部分的差别。

 三、多重背包问题

一般输入两个变量:体积(亦或者是重量)v、价值w和数量s

背包问题中最难的了,结合了0-1背包和多重背包的特点,简单来说就是某个物品可以取s次,有了次数限制。

常规思路就是拆分成份,重新构成0-1背包问题。

例题4. 多重背包问题 I - AcWing题库

#include <iostream>
#include <vector>
#include<bits/stdc++.h> 
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int s[1001];
int main() {int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>v1[i]>>w[i]>>s[i];}for(int i=0;i<n;i++){while(s[i]!=0){ //监控数量for(int j=v;j>=v1[i];j--){  //0-1背包处理dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);}s[i]--;}}cout<<dp[v];
}

可以看到,for(int j=v……这部分的处理和0-1背包的处理逻辑一样。就是在外面增加一个while监控数量的变化即可。整体还是在for(int i=0;i<n;i++){框架下。

上述的微小改进只适用于处理小范围数据集,数据集一大(一两千)就会超时,此时就需要改进算法了,参考下题:

数据量大的情况:5. 多重背包问题 II - AcWing题库

二进制优化是基于这样的事实:

任意正整数可以表示为2的幂之和。

利用这一点,我们可以将每种物品的数量拆分成几个二进制的组件,从而将多重背包问题转换为0-1背包问题的多个实例。

二进制拆分挺麻烦的……要加里面,我写了一版有的用例没有过,还需要再背2024年5月6日

#include <bits/stdc++.h>
using namespace std;
int dp[2102];
int v1[2101];
int w[2101];
int s[2001];int main() {int n,v;cin>>n>>v;for(int i=0;i<n;i++){cin>>v1[i]>>w[i]>>s[i];}for(int i=0;i<n;i++){if(s[i]*v1[i]>=v){ //份数乘以重量 大于 容量,采取完全背包。 for(int j=v1[i];j<=v;j++){dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);}}else{// 二进制拆分,处理多重背包问题for(int k=1;s[i]>0;k=k*2){if(k>s[i]){// 当拆分块大于剩余数量时,调整k为剩余数量k=s[i];}int totalv=k*v1[i];int totalw=k*w[i];for(int j=v;j>=totalv;j--){//0-1背包处理 dp[j]=max(dp[j],dp[j-totalv]+totalw);}s[i]=s[i]-k;}}}cout<<dp[v];return 0;
}

四、分组背包问题 

分组背包问题:9. 分组背包问题 - AcWing题库

就是分组,每个组只能取一个背包。(这个模板没背过,下次记得背,2024年5月6日)

#include <bits/stdc++.h>
using namespace std;
int dp[102];
int v1[101];
int w[101];int main() {int n,v,z;cin>>n>>v;for(int i=0;i<n;i++){cin>>z;for(int j=0;j<z;j++){			cin>>v1[j]>>w[j];}for(int k=v;k>=0;k--){for(int j=0;j<z;j++){if(k>=v1[j]){dp[k]=max(dp[k],dp[k-v1[j]]+w[j]);	}}}}cout<<dp[v];return 0;
}

http://www.lryc.cn/news/341863.html

相关文章:

  • [DEMO]给两个字符串取交集的词语
  • leetcode53-Maximum Subarray
  • Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单人脸检测/识别实战案例 之七 简单进行人脸检测并添加面具特效实现
  • 【go项目01_学习记录06】
  • Vue中Element的下载
  • 机器人项目相关
  • Mac升级go版本某种错误情况处理
  • 美团KV存储squirrel和Celler学习
  • Python学习笔记------处理数据和生成折线图
  • 知识图谱与大语言模型的协同(RAG)——MindMap
  • 奶爸预备 |《P.E.T.父母效能训练:让亲子沟通如此高效而简单:21世纪版》 / 托马斯·戈登——读书笔记
  • 【WebGIS实例】(13)MapboxGL 加载地形高程数据
  • Node.js -- MongoDB
  • 语音识别--单声道转换与降采样
  • 基于springboot+vue+Mysql的点餐平台网站
  • 数据库优化
  • 专业渗透测试 Phpsploit-Framework(PSF)框架软件小白入门教程(一)
  • Web安全研究(七)
  • 矩池云jupyter运行opengait代码 未完成版
  • 油烟净化器买家必看!商用油烟净化器功效及使用方法盘点
  • gitee关联picgo设置自己的typora_图床
  • 深入理解网络原理1
  • 为什么感觉没有效果
  • C++中的指针详解
  • 视频改字祝福 豪车装X系统源码uniapp前端小程序源码
  • google chromeDriver 地址
  • 分布式与一致性协议之Raft算法(一)
  • 从自定义一个作用域开始来了解SpringBean的作用域
  • Android 编译文件简述(Android.mk)
  • [React] 手动实现CountTo 数字滚动效果