当空间优化成一维之后，只有完全背包问题的体积是从小到大循环的。

枚举顺序：

1
2
3
for 物品
  for 体积
    for 决策

423. 采药

01 背包问题

总限制时间是背包体积，每棵草药相当于物品，草药价值是物品价值，采集草药花费的时间是物品所占空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

const int N = 1010;
int f[N], w[N], v[N];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> v[i] >> w[i];
  for (int i = 1; i <= m; i++) {
    for (int j = n; j >= v[i]; j--) {
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
  }
  cout << f[n] << endl;
  return 0;
}

1024. 装箱问题

01 背包问题

物品价值就是体积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

const int N = 20010;

int f[N], v[N];

int n, m;

int main() {
  cin >> m >> n;
  for (int i = 1; i <= n; i++) cin >> v[i];
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
      f[j] = max(f[j], f[j - v[i]] + v[i]);
    }
  }
  cout << m - f[m] << endl;
  return 0;
}

1022. 宠物小精灵之收服

二维费用 01 背包问题：f(i,j,k)f(i, j, k) 表示所有只从前 i 个物品中选，花费 1 不超过 i，花费 2 不超过 k 的选法的最大价值。

本题 f(i,j,k)f(i, j, k) 含义为：只从前 i 个野生小精灵中选，需要的精灵球的数量不超过 j，对皮卡丘造成的伤害不超过 k 的选法中，最多能收服的野生小精灵数量。

皮卡丘受到的最小伤害可以通过寻找满足 f[i][j][t] == f[K][N][M - 1] 的最小的 t 来求出。M - 1 是因为皮卡丘体力等于 0 时，野生小精灵也不会被收服。

皮卡丘剩余的最大体力用总体力值 - t 来求出。

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
#include <iostream>
using namespace std;

const int N = 1010, M = 510;
int V1, V2;
int n;
int f[N][M], v1[N], v2[N];

int main() {
  cin >> V1 >> V2 >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v1[i] >> v2[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = V1; j >= v1[i]; j--) {
      for (int k = V2 - 1; k >= v2[i]; k--) {
        f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
      }
    }
  }
  cout << f[V1][V2 - 1] << ' ';
  int k = V2 - 1;
  while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;
  cout << V2 - k << endl;
  return 0;
}

6. 多重背包问题 III

多重背包问题 III DP 分析

列举几个状态转移方程：

f(i,j)=max{f(i−1,j),f(i−1,j−vi)+wi,f(i−1,j−2vi)+2wi,… ,f(i−1,j−sivi)+swi}f(i, j) = max\{f(i-1, j), f(i-1, j-v_i) + w_i, f(i-1,j-2v_i) + 2w_i, \dotso, f(i-1, j-s_iv_i) + sw_i\}

f(i,j−vi)=max{f(i−1,j−vi),f(i−1,j−2vi)+wi,f(i−1,j−3vi)+2wi,… ,f(i−1,j−sivi)+(si−1)wi,f(i−1,j−(si+1)vi)+siwi}f(i, j-v_i) = max\{f(i-1, j-v_i), f(i-1, j-2v_i) + w_i, f(i-1,j-3v_i) + 2w_i, \dotso, f(i-1, j-s_iv_i) + (s_i-1)w_i, f(i-1, j-(s_i+1)v_i) + s_iw_i\}

f(i,j−2vi)f(i, j-2v_i)

f(i,j−3vi)f(i, j-3v_i)

…\dotso

观察上面几个状态的式子，可以发现：

转移只会发生在「对当前物品体积取余相同」的状态之间。

可以利用某个状态必然是由余数相同的特定状态值转移而来进行优化。

对于每个状态 f(i,j)f(i, j) 的求解，都是求 f(i−1,j−vi),f(i−1,j−2vi),f(i−1,j−3vi),… ,f(i−1,r+vi),f(i−1,r)⏞共si个\overbrace{f(i-1, j-v_i), f(i-1, j-2v_i), f(i-1, j-3v_i), \dotso, f(i-1, r + v_i), f(i-1, r)}^{共s_i个} 的最大值，其中 r=j mod vir = j \bmod v_i，对于不足 sis_i 个的情况，有多少算多少，然后再与 f(i−1,j)f(i-1, j) 取一次 max.

同理，求 f(i,j−vi)f(i, j-v_i) 时，要求出从 f(i−1,j−2vi)f(i-1, j-2v_i) 开始共 sis_i 个状态的最大值，再与 f(i−1,j−vi)f(i-1, j-v_i) 求最大值。

可以装化为求滑动窗口内的最大值，使用单调队列求解。

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
#include <cstring>
#include <iostream>
using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main() {
  cin >> n >> m;
  // 枚举每个物品 i
  for (int i = 0; i < n; i++) {
    int v, w, s;
    cin >> v >> w >> s;
    memcpy(g, f, sizeof f);
    // j 是 当前背包容量 / 当前物品体积的余数，枚举余数。
    for (int j = 0; j < v; j++) {
      int hh = 0, tt = -1;
      // 枚举余数相同情况下的所有状态 f[k]，例如：f[j], f[j + v], f[j + 2v], ...
      for (int k = j; k <= m; k += v) {
        // q[hh] 存的是一个状态 f[x]，当滑出窗口之后，把它从队列弹出
        if (hh <= tt && q[hh] < k - s * v) hh++;
        if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
        while (hh <= tt &
               g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
          tt--;
        q[++tt] = k;
      }
    }
  }
  cout << f[m] << endl;
  return 0;
}
1
2
3
4
5
j = 0，余数为 0，当前物品体积为 v = 2，个数为 s = 3
f[0] f[2] f[4] f[6] f[8] f[10]
     --- 长度为 s --
 ^    ^               ^
q[hh] k-sv            k

当 q[hh] < k - s * v 时，说明队头已经不在滑动窗口中了，把队头弹出。