信息学奥赛一本通 1270:混合背包(evd)
发布日期:2022-01-30 02:41:39 浏览次数:14 分类:技术文章

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

【题目描述】

一个旅行者有一个最多能装V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn。有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

【输入】

第一行:二个整数,M(背包容量,M≤200),N(物品数量,N≤30);

第2…N+1行:每行三个整数Wi,Ci,Pi,前两个整数分别表示每个物品的重量,价值,第三个整数若为0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多件数(Pi)。

【输出】

仅一行,一个数,表示最大总价值。

【输入样例】

10 3
2 1 0
3 3 1
4 5 4
【输出样例】
11
【心得】根据物品的数量选择背包的方式而已!1+1=2!
【AC代码】

#include
#include
#include
using namespace std;const int N=35;int c[N],p[N],w[N],f[7*N];int main(){
int n,m; cin>>m>>n; for(int i=1;i<=n;i++) {
cin>>w[i]>>c[i]>>p[i]; } for(int i=1;i<=n;i++) {
if(p[i]==0) {
for(int j=w[i];j<=m;j++) f[j]=max(f[j],f[j-w[i]]+c[i]); } else {
for(int j=m;j>=w[i];j--) {
for(int k=1;k<=p[i];k++) {
if(j-k*w[i]>=0) f[j]=max(f[j],f[j-k*w[i]]+k*c[i]); } } } } cout<

转载地址:https://blog.csdn.net/everwide1982/article/details/110006674 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:信息学奥赛一本通 1269:庆功会(evd)
下一篇:信息学奥赛一本通 1290:采药(evd)

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月25日 21时17分38秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java ajax教程_(转)JAVA AJAX教程第三章—AJAX详细讲解 2019-04-21
java operators_A guide to Java Operators 2019-04-21
java socket调试_JAVA实现SOCKET多客户端通信的案例 2019-04-21
java 使用或覆盖了已过时的api_JAVA使用或覆盖了已过时的 API 2019-04-21
java 图片旋转保存_Java 对图片90度旋转 2019-04-21
用java实现文学研究助手_数据结构文学研究助手 C语言代码实现(带源码+解析)... 2019-04-21
java gc的几种方式_GC 的三种基本实现方式 2019-04-21
wget linux java 32_通过wget在Linux上下载Java JDK会显示在许可证页面上 2019-04-21
babylonjs 设置面板位置_babylonjs 空间坐标转为屏幕坐标 2019-04-21
oracle里面如何查询sqlid,CSS_oracle中如何查看sql, --查询表状态:  select uo.O - phpStudy... 2019-04-21
oracle 查询中用case,oracle case when 在查询时候的用法。 2019-04-21
oracle正在运行的程序包,ORACLE PL/SQL编程详解之程序包的创建与应用 2019-04-21
php局部页面滚动,在访问另一页面后保留浏览器滚动位置 - php 2019-04-21
jmeter运行linux命令行,Jmeter在linux上运行(命令行运行Jmeter) 2019-04-21
linux服务器怎么添加站点,如何增加站点或虚拟主机及文件说明 2019-04-21
linux系统输入指令,Linux系统基础 - 基本操作命令 2019-04-21
linux设备管理命令,Linux命令(设备管理).doc 2019-04-21
linux 中文utf-8转gbk编码,Linux平台下 GBK编码转UTF-8编码 2019-04-21
linux安装软件在boot,在Linux系统上安装Spring boot应用的教程详解 2019-04-21
linux进入用户user1主目录,Linux系统命令提示符为[user1@localhost root]当前用户所在目录为( )... 2019-04-21