加工厂网站建设,公共信息服务平台官网,商务服务平台,wordpress缩略图变形注意事项#xff1a; 本题是动态规划—01背包和背包模型—二维费用的背包问题的扩展题#xff0c;优化思路不多赘述#xff0c;dp思路会稍有不同#xff0c;下面详细讲解。
题目#xff1a; 潜水员为了潜水要使用特殊的装备。
他有一个带2种气体…注意事项 本题是动态规划—01背包和背包模型—二维费用的背包问题的扩展题优化思路不多赘述dp思路会稍有不同下面详细讲解。
题目 潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸一个为氧气一个为氮气。 让潜水员下潜的深度需要各种数量的氧和氮。 潜水员有一定数量的气缸。 每个气缸都有重量和气体容量。 潜水员为了完成他的工作需要特定数量的氧和氮。 他完成工作所需气缸的总重的最低限度的是多少
例如 潜水员有5个气缸。每行三个数字为氧氮的升量和气缸的重量
3 36 12010 25 1295 50 2501 45 1304 20 119如果潜水员需要5升的氧和60升的氮则总重最小为24912或者45号气缸。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式 第一行有2个整数 mn。它们表示氧氮各自需要的量。 第二行为整数 k表示气缸的个数。 此后的 k行每行包括aibici3个整数。这些各自是第 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; ic; 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; ic; i) {for (int j n; j0; j--) {for (int k m; k0; k--) {//题目所说的是当方案的v1不小于n且v2不小于m时w的最小值也就是说可能用到超过n和m的物品也就会出现负数的情况//这也就是为什么j0,k0,而不是jv1[i],kv2[i]//例如f[2][5],也就是需要v1不小于2v2不小于5那么如果有一个物品v1是3v2是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的最小值也就是说可能用到超过j和k的物品也就会出现 j-v1[i]或者k-v2[i]负数的情况。
这也就是为什么j0,k0而不是jv1[i],kv2[i]。
例如f[2][5],也就是需要物品v1不小于2v2不小于5 那么如果有一个物品v1是3v2是4那么这个物品照样能用只是多出了一些体积但是仍然符合条件 就可以转移为f[0][1] w, 此时就不需要v1了因为v1满了只需要看v2即可负数也能用换为0即可。
声明 算法思路来源为y总详细请见https://www.acwing.com/ 本文仅用作学习记录和交流
