HDU 3349 Consumer

​​题目链接​​

题目背景

有依赖的背包，下面用我常用的变量和说法。

题目大意

有个主件和块钱，每个主件都有费用和对应的个附件，附件也有费用与价值，购买主件后才能购买附件，问怎样购买才能使得到的价值最大。

输入格式

输入有多组，每组询问第一行是整数主件个数（）和总钱数（），接下来有行，每行先输入两个整数主件费用（）和附件个数（），然后有对数表示附件的费用（）和价值（）

我们通过完善背包九讲中对有依赖背包的阐述来处理这道题：
我们可以对主件的附件集合先进行一次01背包（在本题中，该附件集合大小即为），得到费用依次为所有这些值时相应的最大价值（即为总钱数去掉主件的费用后剩下的钱数，在一种可能的情况下这些钱都用来购买该主件和其下的附件）。那么这个主件及它的附件集合相当于有个物品的物品组（因为一共有那么多数），其中费用为的物品的价值为（此题中主件没有价值），该物品组中你只能选一件物品，因为每个物品即对应着一种附件选法。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件及其附件转化为个物品的物品组，就可以直接应用分组背包的算法解决问题了。
再进一步说明一下，数组中存储的是“在的花费下，该组内的附件能提供的最大价值”。

回顾一下普通分组背包的做法：

for (int i = 1; i <= n; i++) {
    cin >> s;
    for (int j = 1; j <= s; j++) cin >> c[j] >> w[j];
    for (int j = V; j >= 0; j--)
        for (int k = 1; k <= s; k++)
            if (j >= c[k])
                f[j] = max(f[j], f[j - c[k]] + w[k]);
}

分组背包是通过外层枚举背包容量来更新状态，同时倒序保证了每组物品中只有一个被选，不断更新费用下的最大价值。

按照上面的解释写出代码：

#include <bits/stdc++.h>
#define A 100010

using namespace std;
int n, V, v, w, c, m, f[A], f_last[A];

int main(int argc, char const *argv[]) {
  while (~scanf("%d%d", &n, &V)) { //n主件个数，V总钱数 
    memset(f, 0, sizeof(f));
      for (int i = 1; i <= n; i++) {
        memcpy(f_last, f, sizeof(f_last)); //需要继承上一组物品的最优情况，可避免使用二维数组
      // ↑相当于实现第二次背包
      scanf("%d%d", &v, &m); //v主件费用，m附件个数 
          for (int k = 1; k <= m; k++) {
            scanf("%d%d", &c, &w); //c附件费用、w附件价值 
            for (int j = V - v; j >= c; j--)
          f_last[j] = max(f_last[j], f_last[j - c] + w);
      }
      for (int j = v; j <= V; j++) f[j] = max(f[j], f_last[j - v]);
      // f数组为加上主件的费用后的最大价值
      }
      printf("%d\n", f[V]);
  }
}