hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活 --多重背包
发布日期:2021-10-03 20:32:30
浏览次数:2
分类:技术文章
本文共 1631 字,大约阅读时间需要 5 分钟。
原题链接:
一:原题内容
Problem Description
急!灾区的食物依然短缺! 为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。 请问:你用有限的资金最多能采购多少公斤粮食呢? 后记: 人生是一个充满了变数的生命过程,天灾、人祸、病痛是我们生命历程中不可预知的威胁。 月有阴晴圆缺,人有旦夕祸福,未来对于我们而言是一个未知数。那么,我们要做的就应该是珍惜现在,感恩生活—— 感谢父母,他们给予我们生命,抚养我们成人; 感谢老师,他们授给我们知识,教我们做人 感谢朋友,他们让我们感受到世界的温暖; 感谢对手,他们令我们不断进取、努力。 同样,我们也要感谢痛苦与艰辛带给我们的财富~
Input
输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据,每行包含3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
Output
对于每组测试数据,请输出能够购买大米的最多重量,你可以假设经费买不光所有的大米,并且经费你可以不用完。每个实例的输出占一行。
Sample Input
18 22 100 44 100 2
Sample Output
400
二:分析理解
一个多重背包模板题。。
三:AC代码
#include#include using namespace std;struct Node{ int price; int weight; int number;};int n, m;Node node[110];int dp[110];void ComplatePack(int cost, int weight){ for (int i = cost; i <= n; i++) dp[i] = max(dp[i], dp[i - cost] + weight);}void ZeroOnePack(int cost, int weight){ for (int i = n; i >= cost; i--) dp[i] = max(dp[i], dp[i - cost] + weight);}void MultiplePack(int cost, int weight, int number){ if (cost*number >= n) { ComplatePack(cost, weight); return; } int k = 1; while (k < number) { ZeroOnePack(k*cost, k*weight); number -= k; k *= 2; } ZeroOnePack(number*cost, number*weight);}int main(){ int test; scanf("%d", &test); while (test--) { scanf("%d%d", &n, &m); memset(dp, 0, sizeof(dp)); for (int i = 0; i < m; i++) scanf("%d%d%d", &node[i].price, &node[i].weight, &node[i].number); for (int i = 0; i < m; i++) MultiplePack(node[i].price, node[i].weight, node[i].number); printf("%d\n", dp[n]); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/51235376 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年03月17日 16时04分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
京东咚咚架构演进
2019-04-21
if....else....使用思考
2019-04-21
Ueditor1.4.3上传图片参照宽度或高度进行压缩(默认最长边)
2019-04-21
O365结合ADFS限制用户登录地址 (一) - 开篇介绍
2019-04-21
我的友情链接
2019-04-21
讲一讲TCP协议
2019-04-21
蓝屏故障的原因及windows蓝屏错误代码
2019-04-21
命令行发布jar到nexus私服
2019-04-21
微信路况会不会超越地图导航?
2019-04-21
存储系统设计——NVMe SSD性能影响因素一探究竟
2019-04-21
Angular JS 简单实例
2019-04-21
阿里云图数据库GraphDB上线,助力图数据处理
2019-04-21
免费主机屋空间mysql和mssql数据库备份和还原技巧
2019-04-21
只需10分钟!就能用Flask,Docker和Jenkins部署机器学习模型
2019-04-21
elastix2.5&vtigercrm5.2.1来电弹屏和点击呼叫的配置
2019-04-21
1-7-RHEL LINUX 文件权限管理
2019-04-21
我的友情链接
2019-04-21
Lucene系列:(8)搜索结果摘要
2019-04-21
Linux系统管理-(20)-awk
2019-04-21
hibernate mapping 主键配置方式
2019-04-21