Luobuyu's Blog

0%

1020. 潜水员

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 1.9k 阅读时长 ≈ 2 分钟
二维背包，至少超过背包容量，求最小值。

1020.潜水员

题目描述：

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

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

1
2
3
4
5
6
7
8
9
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$

题解：

背包问题，至少包含背包容量。而且只能求最小值，因为最大值就是所有的相加。

假设 $dp[i][j][k]$ 表示前 $i$ 个物品，装进背包，容量至少大于等于 $j,k$ 的最小花费。则根据01背包，可以得出：

而且初始值是 $dp[0][0][0] = 0$ ，因为什么都不装时，就满足条件了。而且当 $j-a_{ij}, k-a_{ik}$ 小于 $0$ ，也能选。说明此时加入 $a_i$ 肯定会大于等于了 $j,k$ 。因此至少背包，需要遍历的范围是 $0\le j \le m, 0\le k \le n$ 。

初始时，全置为 $INF$ ， $dp[0][0][0] = 0$ ，然后使用01背包循环。

恰好装满背包和容量不超过背包容量都需要 $a_{ij} \le j \le m, a_{ik} \le k \le n$ 。

求方案数时，

体积至少和恰好都需要初始化 $dp[0][0][0] = 1$ 。

体积至多需要初始化 $dp[0][j][k] = 1, 0\le j \le m, 0\le k \le n$ 。因为是前 $0$ 个物品，一个都不装，方案数为 $1$ 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k, v;
int a[maxn][3];
int dp[maxn][maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    read(m, n, t);
    for (int i = 1; i <= t; ++i)
    {
        read(a[i][0], a[i][1], a[i][2]);
    }
    // dp[i][j][k] 表示前 i 个至少装满 j,k 所需要的最小重量
    // dp[i][j][k] = min(dp[i-1][j][k], dp[i - 1][j - aij][k - aik] + aiv);
    // 初始化为无穷大，dp[0][0][0] = 0;
    // 当 j - aij 为负值时，其实表示 aij 可以装满 j，直接用 max(0, j - aij), max(0, k - aik)

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= t; ++i)
    {
        for (int j = m; j >= 0; --j)
        {
            for (int k = n; k >= 0; --k)
            {
                dp[j][k] = min(dp[j][k], dp[max(0, j - a[i][0])][max(0, k - a[i][1])] + a[i][2]);
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}