潜水员为了潜水要使用特殊的装备。
他有一个带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$。它们表示氧,氮各自需要的量。
第二行为整数 $k$ 表示气缸的个数。
此后的 $k$ 行,每行包括$a_i,b_i,c_i$,3个整数。这些各自是:第 $i$ 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
$1 \le m \le 21$,
$1 \le n \le 79$,
$1 \le k \le 1000$,
$1 \le a_i \le 21$,
$1 \le b_i \le 79$,
$1 \le c_i \le 800$
输入样例:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例:
249
思路
这个题和普通二维背包不同点在于这个题要求至少需要的重量
直接转化成学过的背包问题就好了
根据题目意思也就设状态方程为f[i][j][k] 从前i个物品(气缸)中选,满足体积(氧气)至少为j,重量(氮气)至少为k的最小价值
f[i][j][k] = min(f[i - 1][j][k], f[i - 1][j - v][k - m])
这个题是要求体积和重量至少是多少,跟正常的背包问题(体积,重量最多为多少)不同
方程其实很容易就能设的出来,要考虑一下优化,因为第i-1层的状态和第i层的状态一样,所以优化方式跟01背包一样。
当 j < v[i] 的时候 如果按最大价值来理解的话 就是背包装不下了,因此最大为 j
而对于至少来说j最少是v[i],因此 j 是可以小于v[i]的,小于v[i]的话其实也就等价于求体积至少为0的最小价值,质量同理 因此修改一下状态方程
f[i][j][k] = min(f[i - 1][j][k], f[i - 1][max(0 ,j - v[i]][max(0, k - m[i]]) + w[i];
#include "bits/stdc++.h"
using namespace std;
const int N = 1010;
int f[N][N];
int m, n, k;
int a[N], b[N], c[N];
signed main(void) {
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i] >> c[i];
}
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= k; i++) {
for (int j = n; j >= 0; j--) {
for (int k = m; k >= 0; k--) {
f[j][k] = min(f[j][k], f[max(j - a[i], 0)][max(k - b[i], 0)] + c[i]);
}
}
}
cout << f[n][m] << '\n';
return 0;
}