信息学奥赛一本通 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.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
babylonjs 设置面板位置_babylonjs 空间坐标转为屏幕坐标
2019-04-21
oracle 查询中用case,oracle case when 在查询时候的用法。
2019-04-21
oracle正在运行的程序包,ORACLE PL/SQL编程详解之程序包的创建与应用
2019-04-21
php局部页面滚动,在访问另一页面后保留浏览器滚动位置 - php
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