当前位置：首页 > news >正文

C++---背包模型---潜水员（每日一道算法2023.3.12）

news 2025/8/24 19:08:48

注意事项：
本题是"动态规划—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 <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
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;
}