DP

动态规划

DP 问题

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

方法

1. 把这道题的 dp 状态和方程写出来
2. 根据它们写出 dfs 函数
3. 添加记忆化数组

const int MMAX = 100;
int tcost[MMAX + 10];
int mget[MMAX + 10];
int mem[MMAX + 5][1000 + 5];
int t, n;
int dfs(int pos, int tleft)
{
    if (mem[pos][tleft] != -1)
        return mem[pos][tleft];
    if (pos == n + 1)
        return mem[pos][tleft] = 0;
    int dfs1, dfs2 = -0x80000000;
    dfs1 = dfs(pos + 1, tleft);
    if (tleft >= tcost[pos])
        dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];
    return mem[pos][tleft] = max(dfs1, dfs2);
}
int main()
{
    memset(mem, -1, sizeof(mem));
    cin >> t >> n;
    for (int i = 1; i <= n; i++)
        cin >> tcost[i] >> mget[i];
    cout << dfs(1, t) << endl;
    return 0;
}

背包 DP

01 背包问题

状态转移方程如下
$$
f[j] = \max(f[j], f[j - w[i]] + v[i])
$$

int N, M;
int tcost[NMAX + 5];
int mget[NMAX + 5];
int ans[MMAX + 5];
int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        cin >> tcost[i] >> mget[i];
    for (int i = 1; i <= N; i++)
    {
        for (int j = M; j >= tcost[i]; j--)
            ans[j] = max(ans[j - tcost[i]] + mget[i], ans[j]);
    }
    cout << ans[M] << endl;
    return 0;
}

完全背包问题

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

int tcost[MMAX + 5];
int mget[MMAX + 5];
long long ans[TMAX + 5];
int main()
{
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
        cin >> tcost[i] >> mget[i];
    for (int i = 1; i <= m; i++)
    {
        for (int j = tcost[i]; j <= t; j++)
            ans[j] = max(ans[j - tcost[i]] + mget[i], ans[j]);
    }
    cout << ans[t] << endl;
    return 0;
}

多重背包问题

多重背包问题是 0-1 背包问题的一个变种，与 0-1 背包的区别在于每种物品的数量不再是 1 个，而是有限个。

for (int i = 1; i <= n; i++) {
  for (int weight = W; weight >= w[i]; weight--) {
    // 多遍历一层物品数量
    for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
      dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
    }
  }
}

混合背包问题

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 k 次。

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

二维背包问题

0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

分组背包问题

从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了

for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])             // 背包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

背包的第 k 优解

memset(dp, 0, sizeof(dp));
int i, j, p, x, y, z;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < n; i++) scanf("%d", &w[i]);
for (i = 0; i < n; i++) scanf("%d", &c[i]);
for (i = 0; i < n; i++) {
  for (j = m; j >= c[i]; j--) {
    for (p = 1; p <= K; p++) {
      a[p] = dp[j - c[i]][p] + w[i];
      b[p] = dp[j][p];
    }
    a[p] = b[p] = -1;
    x = y = z = 1;
    while (z <= K && (a[x] != -1 || b[y] != -1)) {
      if (a[x] > b[y])
        dp[j][z] = a[x++];
      else
        dp[j][z] = b[y++];
      if (dp[j][z] != dp[j][z - 1]) z++;
    }
  }
}
printf("%d\n", dp[m][K]);