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

本文共 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

你可能感兴趣的文章
RTS打卡计划第四周
查看>>
C#_delegate - Pair<T> 静态绑定
查看>>
成都OpenPart——DevOps专场活动参与感
查看>>
Delphi xe6 android Popup控件的使用
查看>>
浅谈linux读写同步机制RCU
查看>>
三层架构设计理念
查看>>
spring的@Transactional
查看>>
java 中生成随机验证码
查看>>
计划任务启动停止控制台程序
查看>>
04-单表查询
查看>>
[ZJOI2006]皇帝的烦恼
查看>>
HTML5简介
查看>>
Read All About It-Attraction舞团
查看>>
[摘录]第1章 开局谈判技巧
查看>>
as 运算符
查看>>
基本数据类型对象包装类
查看>>
1178:成绩排序
查看>>
php总结8——mysql函数库、增删改
查看>>
20170914-构建之法:现代软件工程-阅读笔记
查看>>
HDU5616 天平能否称出物体重量问题 01背包变形或者折半搜索
查看>>