题目描述

潜水员为了潜水要使用特殊的装备。

他有一个带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 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。

输出格式

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

数据范围

1 ≤ m ≤ 21,
1 ≤ n ≤ 79,
1 ≤ k ≤ 1000,
1 ≤ ai ≤21,
1 ≤ bi ≤79,
1 ≤ ci ≤800

输入样例

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

输出样例

249

算法 二维费用的背包问题

这个题与常见的二维费用背包问题的最大区别是 ‘至少’ 和 ‘最低值’
本题的容量是无限大 但是结果要满足氧气和氮气的’至少量’ 且 总重量为’最低值’
当加入的氧气含量或者氮气含量使得总含量大于至少含量 (常规背包的容积) 也是符合条件的

用f[k, i, j]表示在前k个气缸中选择 使得氧气含量至少是i, 氮气含量至少是j 从而有两种选法
1.不选第k个 f[k - 1, i, j]
2.选择第k个 min(f[k - 1, i , j], f[k - 1, i - v1, j - v2] + w)
在第二种情况下 v1是可以大于i, v2是可以大于j的 因为f为氧气氮气含量至少为i, j, 也可以多于i和j
所以要改为 min(f[k - 1, i, j], f[k - 1, max(0, i - v1), max(0, j - v2)])

打卡代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int M = 50, N = 100;

int m, n, k;
int f[M][N];

int main()
{
    cin >> m >> n >> k;

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    while (k -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        for (int i = m; i >= 0; i -- )
            for (int j = n; j >= 0; j -- )
                f[i][j] = min(f[i][j], f[max(0, i - a)][max(0, j - b)] + c);

    }

    cout << f[m][n] << endl;
    return 0;
}