HDU3449 Consumer 条件背包 DP

这道题应该是背包问题里堪称经典的问题了，表示刚开始学 DP，这类问题也很快弄懂了。

题目大意

给你一些分组，每组物品放在一个盒子里，每组物品都有几种物品，有自己的价格 $c$ 和价值 $v$，现在要买一个物品时，要买它对应的盒子，盒子的价格是 $p$，问你花一定的钱最多买到的物品价值是多少。

这类问题要用到两个数组，$dp[0][i]$ 表示 $i$ 块钱可以买到的最大价值，$dp[1][i]$ 表示考虑到当前盒子时，$i$ 块钱可以买到的最大价值，首先 $dp[0]$ 置为 $0$，枚举全部的盒子，$dp[1]$ 置为$-\infty$ 表示买不到，更新的转移可以从 $dp[0]$ 转移也可以从 $dp[1]$ 转移，从 $dp[0]$ 转移表示你还没有买盒子，要附加上盒子的价格，$dp[1]$ 表示你买过盒子了，就直接转移就可以了，转移方程如下:

$$dp[1][k] = \max \begin{cases} dp[1][k] \\ dp[1][k-c[i][j]]+v[i][j] \\ dp[0][k-c[i][j]-p[i]]+v[i][j] \end{cases}$$

注意每次 $dp[1]$ 的置 $-\infty$ 操作，以及每次枚举完当前盒子后用 $dp[1]$ 更新 $dp[0]$ 的值。

$$dp[0][j]=\max(dp[0][j],dp[1][j])$$

我的完整代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int oo = 0x3f3f3f3f;

int dp[2][100100];
int p[60], m[60];
int c[60][12], v[60][12];

int main() {
  int n, w;
  while (~scanf("%d%d", &n, &w)) {
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &p[i], &m[i]);
      for (int j = 0; j < m[i]; j++) {
        scanf("%d%d", &c[i][j], &v[i][j]);
      }
    }
    for (int i = 0; i <= w; i++) {
      dp[0][i] = 0;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= w; j++) {
        dp[1][j] = -oo;
      }
      for (int j = 0; j < m[i]; j++) {
        for (int k = w; k >= c[i][j]; k--) {
          if (dp[1][k - c[i][j]] >= 0 &&
              dp[1][k] < dp[1][k - c[i][j]] + v[i][j])
            dp[1][k] = dp[1][k - c[i][j]] + v[i][j];
          if (k >= c[i][j] + p[i])
            dp[1][k] = max(dp[1][k], dp[0][k - c[i][j] - p[i]] + v[i][j]);
        }
      }
      for (int j = 0; j <= w; j++) {
        dp[0][j] = max(dp[0][j], dp[1][j]);
      }
    }
    printf("%d\n", *max_element(dp[0], dp[0] + w + 1));
  }
  return 0;
}