一本通-1271：【例9.15】潜水员（二维01背包）

【题目描述】 潜水员为了潜水要使用特殊的装备。他有一个带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）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。

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

【输入样例】 5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119

【输出样例】 249

---

这道题和以往的题目还是不太一样，以往都是让价值最大，并且重量不能超过背包容量。现在是需要找物品，让氧气量和氮气量都超过需求。每种物品只能选一个，肯定逆序遍历。

#include <bits/stdc++.h>

using namespace std;

int m, n, k;
vector<vector<int> > d(25, vector<int>(85, INT_MAX - 1000));

void twoDimensionPack(int oxygen, int nitrogen, int weight)
{
    for (int i = m; i >= 0; --i) {
        for (int j = n; j >= 0; --j) {
            int tmp1 = i + oxygen, tmp2 = j + nitrogen;
            if (tmp1 > m) tmp1 = m;
            if (tmp2 > n) tmp2 = n;
            d[tmp1][tmp2] = min(d[tmp1][tmp2], d[i][j] + weight);
        }
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> n >> k;
    int oxygen, nitrogen, weight;
    d[0][0] = 0;
    for (int i = 0; i < k; ++i) {
        cin >> oxygen >> nitrogen >> weight;
        twoDimensionPack(oxygen, nitrogen, weight);
    }
    cout << d[m][n] << endl;

    return 0;
}