题目大意:
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸:一个为氧气,一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸,每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少?
解题方法:
这题是一个二维费用的背包问题,但这题是体积可以大于要求的数。
所以我们要对转移方程做改变:
f[j][v] = min(f[j][v], f[max(0, j - v1)][max(0, v - v2)] + w);
那你就会问了:为啥小于的时候还可以跟0等价呢?
既然这里已经满足了,那么就不需要这方面的了,所以就相当于还剩0。
完整代码,时间复杂度:$O(nmk)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, k;
int f[30][90];
int main()
{
cin >> n >> m >> k;
memset(f, 0x3f, sizeof f);
f[0][0] = 0;//其实跟刚好的一样
while (k -- ) {
int v1, v2, w;
cin >> v1 >> v2 >> w;
for (int j = n; j >= 0; j -- ) {
for (int v = m; v >= 0; v -- ) {
f[j][v] = min(f[j][v], f[max(0, j - v1)][max(0, v - v2)] + w);
}
}
}
cout << f[n][m] << endl;
}
那我们总结一些规律(对于01背包的三种状态):
$$背包问题中的三种状态$$
- 体积不超过 $v$
$f$ 数组全部初始化为 $0$,计算时严格保证任意状态下背包的体积 $\ge 0$ - 体积恰好是 $v$
$f[i][0]$ 初始化为 $0$, 其他全部初始化为 $inf$,同时也要严格保证任意状态下背包体积 $\ge 0$ - 体积至少是 $v$
$f[i][0]$初始化为 $0$, 其他全部初始化为 $inf$, 任意状态下背包的体积允许 $< 0$
这里总结有问题吧,体积不超过v应该是求最大值吧, 体积恰好是v的初始化应该还要根据是求最大值或者最小值而定, 体积至少是v, 这里求的应该是最小值吧
最大和最小能有啥区别?就变一下正负号就行了啊
肯定有区别啊
您要不说一下啥区别?我不是很懂
这里的f[i][0] 后续都被f[0][0]更新了所以不用单独初始化是吗
你看这里的表示,他表示的是氧气和氮气,他其实没有每个气瓶这一维
我知道你想表达的意思,他没有这一位就等价于全是初始化过了
这个总结很不错
%%%%%%