写在前面

如果这道题大家有疑问的话，可以把 leetcode 这两道题做了，再来看看 01 背包（求至少）

https://leetcode.com/problems/jump-game/description/
https://leetcode.com/problems/jump-game-ii/description/

题目分析

设 所需氧气 为 A，所需氮气 为 B。题目的意思选择若干个气缸，可以使得 Sum(A) >= A, Sum(B) >= B 且重量尽量的轻。
即我们选择的气缸的氧气加起来 至少 为 A，氮气加起来 至少 为 B。

状态表示 和 状态分析

设 f[j][k] 表示我们选择了氧气为 j，氮气为 k 之后，所需的气缸数目最少是多少。

首先这是一个 01 背包问题，求最小值，先将状态初始化。

int f[100][100];
memset(f, 0x3f, sizeof(f));

f[0][0] = 0;

按照 01 背包的做法，我们可以直接写出如下状态转换：（注意，下面的写法是错误的）

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= A; j++) {
        for (int k = 0; k <= B; k++) {
            f[j][k] = f[j][k];
            if (j >= a[i] && k >= b[i]) {
                f[j][k] = min(f[j][k], f[j-a[i]][k-b[i]] + w[i]);
            }
        }
    }
}

首先 f[j][k] 表示的是到了第 n 个气缸之后，我们可以选择第 n 个气缸也可以不选第 n 个气缸：
1. 不选 n 气缸 f[j][k]
2. 选 n 气缸
为了说明 01 背包的解法是错的，我们先来给出正确的写法

f[0][0] = 0;
for (int i = 0; i < n; i++) {
    for (int j = A; j >= 0; j--) {
        for (int k = B; k >= 0; k--) {
            if (j <= a[i] && k <= b[i]) {
                f[j][k] = min(f[j][k], f[0][0] + w[i]);
            } else if (j <= a[i]) {
                f[j][k] = min(f[j][k], f[0][k - b[i]] + w[i]);
            } else if (k <= b[i]) {
                f[j][k] = min(f[j][k], f[j - a[i]][0] + w[i]);
            } else {
                f[j][k] = min(f[j][k], f[j - a[i]][k - b[i]] + w[i]);
            }
        }
    }
}

分析下：为什么在 01 背包的时候， j<a[i] 和 k<b[i] 不能作为取值，因为我们背包的容量只有 j 和 k，放不下 a[i] 和 b[i]。
但是在这里，假设我们把 a[i] 和 b[i] 装进背包，并不会有什么问题，因为 氧气和氮气 超出背包容量依然能满足。如果不装来反而会漏更新状态
其实只要看看我们的判断条件 j <= a[i] && k <= b[i]，表示的是我们只用选择第 i 个背包就能将氧气和氮气填满了，这时候 f[j][k] 直接是 min(f[j][k], w[i])；而 01 背包的做法会漏掉这个状态。

简写：

for (int i = 0; i < n; i++) {
    for (int j = A; j >= 0; j--) {
        for (int k = B; k >= 0; k--) {
            f[j][k] = min(f[j][k], f[max(0, j - a[i])][max(0, k - b[i])] + w[i]);
        }
    }
}