1020 潜水员（二维费用的零一背包问题）

た入场券 2022-09-11 02:28 182阅读 0赞

**1. 问题描述：**

潜水员为了潜水要使用特殊的装备。他有一个带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  
来源：[https://www.acwing.com/problem/content/description/1022/][https_www.acwing.com_problem_content_description_1022]

**2. 思路分析：**

分析题目可以知道这道题目属于选择性的问题，对于每一个气缸我们可以选择也可以不选择，所以属于经典的**零一背包问题**，并且题目中有两个花费（也即体积和重量的限制），氧气的体积大于等于m，氮气的体积大于等于n，由于存在两个花费所以属于经典的**二维费用的零一背包问题**，我们可以将每一个气缸看成是一个物品，需要氧气和氮气的含量看成是体积和重量的限制，价值可以看成是气缸重量的最小值。动态规划一般分为两个步骤：① 状态定义 ② 状态计算；对于状态定义我们可以定义一个二维的数组或者列表dp，其中dp\[i\]\[j\]表示体积至少为j，重量至少是k的气缸重量的最小值；这道题目中体积和重量的限制是"至少"（一般是三种："不超过"，"恰好"，"至少"），对于题目中体积的限制的类型不同初始化和状态计算也是不一样的，对于限制是"至少"的题目所以我们在初始化的时候dp\[0\]\[0\] = 0，dp\[0\]\[0\]是合法的状态，其余的状态都是不合法的，所以初始化为正无穷；状态计算对应集合的划分，我们一般是找最后一个不同点，我们可以根据最后一个物品i选还是不选划分为两个集合，对于体积和重量是"至少"限制的题目，我们在状态计算的时候j - v小于0的时候需要将j - v的状态转移到0这个状态，因为负数的状态其实也是合法的（体积为负数的时候相当于是一件物品都没有选，而物品的体积是大于等于1的所以可以将其转移到0这个状态），这样就满足一开始dp\[i\]\[j\]的状态定义，体积至少为j，重量至少为k的限制。

**3. 代码如下：**

if __name__ == '__main__':
        # 这道题目中氧的含量需要>=m, 氮的含量需要>=n
        V1, V2 = map(int, input().split())
        n = int(input())
        INF = 10 ** 9
        # 一开始的时候初始化所有元素为最大值, 表示这些状态是不合法的, 只有dp[0][0]才是合法的
        dp = [[INF] * (V2 + 1) for i in range(V1 + 1)]
        # 第一个状态是合法的
        dp[0][0] = 0
        for i in range(n):
            v1, v2, w = map(int, input().split())
            for j in range(V1, -1, -1):
                for k in range(V2, -1, -1):
                    # 因为状态定义中的第一维dp[j]大于等于m, 第二维dp[k]大于等于n所以当为负数的时候转移到0这个状态, 这样对应的每一维都是满足状态定义的
                    dp[j][k] = min(dp[j][k], dp[max(0, j - v1)][max(0, k - v2)] + w)
        # 最后的dp[V1][V2]就是答案
        print(dp[V1][V2])

[https_www.acwing.com_problem_content_description_1022]: https://www.acwing.com/problem/content/description/1022/