博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【常用模板】 混合背包
阅读量:6921 次
发布时间:2019-06-27

本文共 796 字,大约阅读时间需要 2 分钟。

混合背包就是把完全、01、多重背包结合起来,循环时判断一下是什么背包就行,完全背包就用完全背包的模板来算,多重和01背包一起算

关键是为什么不能乘k,至今未解,乘了k之后20分,不乘k的话100分

#include 
#include
using namespace std;int f[1100],p[1100],v[1100],w[1100];int main(){ int m,n; cin>>m>>n; for(int i=1;i<=n;i++) { cin>>w[i]>>v[i]>>p[i]; } for(int i=1;i<=n;i++) { if(p[i]==0) //完全背包 { for(int j=w[i];j<=m;j++) if(f[j-w[i]]+v[i]>f[j]) f[j]=f[j-w[i]]+v[i]; } else //01和多重背包 { for(int k=1;k<=p[i];k++) for(int j=m;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+v[i]); } } } cout<

转载于:https://www.cnblogs.com/oiersyp/p/6241635.html

你可能感兴趣的文章
salt安装
查看>>
linux运维基础1
查看>>
Hyper-V Server虚拟机移动性
查看>>
Visual Studio 2014 预览版 CTP3 发布了!可以下载
查看>>
protoc 在linux下的安装
查看>>
jq上百个input 做提交不能为空的验证
查看>>
网络篇
查看>>
全面详解Linux日志管理技巧
查看>>
翻译连载 | 第 11 章:融会贯通 -《JavaScript轻量级函数式编程》 |《你不知道的JS》姊妹篇...
查看>>
去中心化访问HTTP服务集群
查看>>
C语言switch语句的用法详解
查看>>
Linux系统和用户界面 中英文语言修改
查看>>
ELK(ElasticSearch, Logstash, Kibana)搭建实时日志分析平台
查看>>
centos6.9 上docker 的安装 及启动 和运行状态查看
查看>>
Linux安装类型和方法
查看>>
Java面试宝典(2)Java基础部分
查看>>
步入Android江湖 有你才会更精彩
查看>>
2011年度盘点云计算工具典型代表大检兵
查看>>
IT名列跳槽榜前三 软件人才需求爆棚
查看>>
决定留在开源社区
查看>>