JXFCZX — 潜水员(二维背包)
发布日期:2021-07-01 00:18:46
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月22日 17时59分15秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Qt5 在添加 Q_OBJECT 后发现编译出错的原因
2021-07-04
OJ:奇怪的类复制
2021-07-04
OJ:神秘的数组初始化
2021-07-04
MAC 地址(单播、组播、广播地址分类)
2021-07-04
OJ:又一道考察多态的题目
2021-07-04
OJ:一道考察多态的题目
2021-07-04
OJ:析构函数实现多态
2021-07-04
GVRP 的工作机制和工作模式
2021-07-04
ubuntu:xxx is not in the sudoers file. 问题解决
2021-07-04
【转载】java 中变量的存储位置
2021-07-04
【转载】解析 java 按值传递还是按引用传递
2021-07-04
【转载】java final 关键字的几种用法
2021-07-04
ubuntu samba 服务器搭建
2021-07-04
使用 pthread_cancel 引入的死锁问题
2021-07-04
为什么全局变量一定要初始化?
2021-07-04
设置程序崩溃时产生 core 文件的配置
2021-07-04
Android编译问题
2021-07-04
linux shell 查看文件内容
2021-07-04
如何知道我下载的android源码是哪个版本的
2021-07-04
Ubuntu下环境变量该写进哪个文件里
2021-07-04