$$\color{Red}{潜水员:二维费最小值的背包问题}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
潜水员为了潜水要使用特殊的装备。
他有一个带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
证明
本题是最小值的二维背包问题 我们拿来DP的循环分析和正常的最大值二维背包对比区别分析二者的不同
二维最大值背包
for(int j=V1; i>=v1; i--)
for(int k=V2; k>=v2; k--)
f[j][k] = Math.max(f[j][k], f[j - v1][k - v2] + w);
二维最小值背包
for(int j=V1; j>=0; j--)
for(int k=V2; k>=0; k--)
f[j][k] = Math.min(f[j][k], f[Math.max(0, j - v1)][Math.max(0, k - v2)] + w);
倒序遍历是为了防止污染被压缩的第i维度，防止出现把更小的f[i-1][j][k]污染，那为什么这里最小值背包可以遍历到0，然后加入一个和0的最大值判断？
最大值的背包是满足不超过j和k的情况下，能选取的物品价值最大的情况。而最小值背包是至少满足j和k的容量 举例子也就是说f[2][3]的情况下，代表2个氧气 3个氮气的情况，如果存在一个3 2 4的气缸，此时其实按至少满足的思路，是可以选取的，而转移状态，我们计算 2 - 3 = -1 在数组中是越界的，氧气已经攒够了，只需要找3 - 2 = 1个氮气即可，那么其实我们只需要按f[0][1] + 4来转移即可
代码
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int V1;//氧气
static int V2;//氮气
static int f[][] = new int[25][80];
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
for (int i = 0; i < 25; i++) {
Arrays.fill(f[i], 0x3f3f3f3f);
}
f[0][0] = 0;
String s1[] = in.readLine().split(" ");
V1 = Integer.parseInt(s1[0]);
V2 = Integer.parseInt(s1[1]);
int n = Integer.parseInt(in.readLine());
for (int i = 0; i < n; i++) {
String s2[] = in.readLine().split(" ");
int v1 = Integer.parseInt(s2[0]);
int v2 = Integer.parseInt(s2[1]);
int w = Integer.parseInt(s2[2]);
for (int j = V1; j >= 0; j--) {
for (int k = V2; k >= 0; k--) {
f[j][k] = Math.min(f[j][k], f[Math.max(0, j - v1)][Math.max(0, k - v2)] + w);
}
}
}
System.out.println(f[V1][V2]);
}
}
python
f = [[0x3f3f3f3f] * 100 for i in range(30)]
m, n = map(int, input().split())
k = int(input())
f[0][0] = 0
for i in range(k):
a, b, c = map(int, input().split())
for j in range(m, -1, -1):
for k in range(n, -1, -1):
f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + c)
print(f[m][n])
