JXFCZX — 潜水员(二维背包)
发布日期:2021-07-01 00:18:46
浏览次数:4
分类:技术文章
本文共 1205 字,大约阅读时间需要 4 分钟。
题目链接:
时间:1 秒 空间:512 MB题目描述
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸:一个为氧气,一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少?
例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:3 36 120
10 25 129 5 50 250 1 45 130 4 20 119如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。输入
第一行有2整数m,n(1≤m≤21,1≤n≤79)。它们表示氧,氮各自需要的量。
第二行为整数k(1≤n≤1000)表示气缸的个数。此后的k行,每行包括ai,bi,ci(1≤ai≤21,1≤bi≤79,1≤ci≤800)3ai,bi,ci(1≤ai≤21,1≤bi≤79,1≤ci≤800)3整数。这些各自是:第i个气缸里的氧和氮的容量及汽缸重量。
输出
仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。
样例输入
5 60
5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119
样例输出
249
解题思路
二维背包问题,只不过这个背包是可以超出容量的,题上只是说满足他工作的最小重量,只要修改一下就可以了。
Accepted Code:#includeusing namespace std;int dp[25][85], p[1005], q[1005], w[1005];int main() { int n, m, l; scanf("%d%d%d", &m, &n, &l); memset(dp, 0x3f, sizeof(dp)); dp[0][0] = 0; for (int i = 0; i < l; i++) { scanf("%d%d%d", &p[i], &q[i], &w[i]); for (int j = m; j >= 0; j--) { for (int k = n; k >= 0; k--) { int t1 = min(m, j + p[i]), t2 = min(n, k + q[i]); dp[t1][t2] = min(dp[t1][t2], dp[j][k] + w[i]); } } } printf("%d\n", dp[m][n]); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/91046323 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月22日 22时21分02秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Ant内置任务之symlink
2019-05-01
jface databinding:部分实现POJO对象的监测
2019-05-01
深入理解python--线程、进程与协程(1)
2019-05-01
Java--流重点总结初稿
2019-05-01
Html2Servlet--Html代码转换为Servlet小程序
2019-05-01
HTTP认证方式
2019-05-01
图书商城:分类模块
2019-05-01
图书商城:订单模块
2019-05-01
开源全能播放器Vitamio的使用
2019-05-01
使用ViewPager加载页面出现空白
2019-05-01
ImageView scaleType
2019-05-01
RecyclerView notifyItem闪屏问题
2019-05-01
dubbo学习笔记 十一 dubbo-rpc之模块
2019-05-01
motan学习笔记 五 opentracing学习入门
2019-05-01
求列表最长子序列
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
网络编程之 Socket函数 (二)
2019-05-01