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]);
  }
}