C++---背包模型---潜水员(每日一道算法2023.3.12)
创始人
2024-06-02 20:03:25
0

注意事项:
本题是"动态规划—01背包"和"背包模型—二维费用的背包问题"的扩展题,优化思路不多赘述,dp思路会稍有不同,下面详细讲解。

题目:
潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸:一个为氧气,一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少?

例如:
潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:

3 36 12010 25 1295 50 2501 45 1304 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式
第一行有2个整数 m,n。它们表示氧,氮各自需要的量。
第二行为整数 k表示气缸的个数。
此后的 k行,每行包括ai,bi,ci,3个整数。这些各自是:第 i个气缸里的氧和氮的容量及气缸重量。

输出格式
仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。

数据范围
1≤m≤21,
1≤n≤79,
1≤k≤1000,
1≤ai≤21,
1≤bi≤79,
1≤ci≤800

输入:
输出:
#include 
#include 
#include 
#include 
using namespace std;const int N = 1010;
int n, m, c;                // 需要的氧气,需要的氮气,气缸的数量
int v1[N], v2[N], w[N];     // v1[i]物品i的氧气量,v2[i]物品i的氮气量,重量
int f[N][N];int main() {cin >> n >> m >> c;for (int i = 1; i<=c; i++) cin >> v1[i] >> v2[i] >> w[i]; // 输入每个气缸中包含的氧和氮的数量以及它们各自的重量memset(f, 0x3f3f, sizeof f); // 由于我们要求最小值,所以初始化数组f为无穷大f[0][0] = 0; // 当选取0个氧气和0个氮气的方案就是0//二维费用dp,优化参考01背包for (int i = 1; i<=c; i++) {for (int j = n; j>=0; j--) {for (int k = m; k>=0; k--) {//题目所说的是,当方案的v1不小于n,且v2不小于m时,w的最小值,也就是说可能用到超过n和m的物品,也就会出现负数的情况//这也就是为什么j>=0,k>=0,而不是j>=v1[i],k>=v2[i]//例如f[2][5],也就是需要v1不小于2,v2不小于5,那么如果有一个物品v1是3,v2是4,那么这个物品照样能用只是多出了一些体积但是仍然符合条件//就可以转移为f[0][1] + w, 此时就不需要v1了,因为v1满了,只需要看v2即可(也就是负数也能用,换为0即可)。f[j][k] = min(f[j][k], f[max(0, j - v1[i])][max(0, k - v2[i])] + w[i]);}}}cout << f[n][m];return 0;
}

思路:
经典的y式dp法

1.状态表示
f[i][j][k]:考虑前i个物品,体积不小于j,重量不小于k时的所有方案,属性为Min。

v1[i]第i个物品的氧气,v2[i]第i个物品的氮气,w[i]第i个物品的重量

2.状态计算
以 选择/不选择 第i个物品为划分,
1.当不选择第i个物品时:
f[i][j][k] = f[i-1][j][k]
2.当选择第二个物品时:
f[i][j][k] = min(f[i][j][k], f[i-1][j-v1[i]][k-v2[i]] + w[i])

同时由于我们无法开三维数组,那么就将第i维也就是物品维度优化即可,参考01背包的优化方式。

这里还有一点要提醒:
状态表示分析出的是:考虑前i个物品,体积不小于j,重量不小于k时的所有方案,找w的最小值,也就是说可能用到超过jk的物品,也就会出现 j-v1[i]或者k-v2[i]负数的情况。

这也就是为什么j>=0,k>=0而不是j>=v1[i],k>=v2[i]

例如f[2][5],也就是需要物品v1不小于2,v2不小于5,
那么如果有一个物品v1是3,v2是4,那么这个物品照样能用只是多出了一些体积但是仍然符合条件,
就可以转移为f[0][1] + w, 此时就不需要v1了,因为v1满了,只需要看v2即可(负数也能用,换为0即可)。

声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...