潜水员

题目

潜水员为了潜水要使用特殊的装备。他有一个带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（1≤m≤21，1≤n≤79）。它们表示氧，氮各自需要的量。

第二行为整数k（1≤n≤1000）表示气缸的个数。

此后的k行，每行包括ai，bi，ci（1≤ai≤21，1≤bi≤79，1≤ci≤800）3ai，bi，ci（1≤ai≤21，1≤bi≤79，1≤ci≤800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。

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

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

249

思路

两个价值 w1(氧气), w2(氮气), 一个重量 v, 求 w1, w2 至少为 n,m 时的最小总重量 v。

有点像01背包, 都是选择一个物品且有重量和价值, 只不过这里是有两种价值, 没什么歪门邪道, 这俩要求必须满足, 试试扩展一维： f[k][i][j]: k是选择前k个物品, 氧气量为i, 氮气量为j 的总气缸重量 一维是直接枚举, 咱这也直接枚举。

初始化的话因为求的是最小值, 故把所有值都初始化为极大值。 f[0][0] = 0

然后正常01背包即可, 注意从 N, M（最大氧气和氮气）开始逆序枚举, 因为求的是至少, 可以超过。

最后再枚举 n-N, m-M, 求最小的重量即可。

扩展： 当状态不合法时, 取正负无穷。

体积最多为j时, 全部为0, 不能有 j- v < 0 体积恰好为j时, f[0][0] = 0 其余无限大. 不能有 j-v<0 体积至少为j时, f[0][0] = 0 其余无限大, 可以有 j-v < 0, 不过需要将 f[j-v] 变成 f[0], 不能省略, 需要重复计算这一步。

代码

const int N = 50, M = 100;
int f[N][M];
int n, m, t;
 
int main()
{
    cin >> n >> m >> t;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 0; i < t; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        for (int j = N - 1; j >= v1; j--)
            for (int k = M - 1; k >= v2; k--)
                f[j][k] = min(f[j][k], f[j - v1][k - v2] + w);
    }
 
    int res = 0x3f3f3f3f;
    for (int i = n; i <= N - 1; i++)
        for (int j = m; j <= M - 1; j++)
            res = min(res, f[i][j]);
 
    cout << res << endl;
 
    return 0;
}