洛谷 P1064 金明的預算方案 分組DP/有依賴DP

總共有 n n n 元，買 m m m 個物品，每個物品有重要度，并且其中一些物品是捆綁銷售的hhh

要使每件物品的價格乘上重要性的總和最大。

思路：有依賴的背包問題，分為主件和附件，對于每個主件，可以選擇：

1. 不選擇主件
2. 隻選擇主件
3. 選擇主件，然後再選擇附件的一種組合

流程大概如下：

首先周遊所有主件，先考慮選擇該主件時以及 0 到多個附件時的每個價格的最優解（01背包）

然後再将這些價位與不選擇該主件時的情況取最優解

詳見代碼及注釋

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 40000
#define MAXM 70
using namespace std;
int n,m,p[MAXM],v[MAXM],q[MAXM],h[MAXN],f[MAXN];
int main(){
#ifdef WINE
    freopen("data.in","r",stdin);
#endif
    scanf("%d%d",&n,&m); // 總錢數，總個數
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&p[i],&v[i],&q[i]);
        v[i]*=p[i]; // 價格乘重要度
    }
    // f[n] 表示花費 n 得到的最大值
    for(int i=1;i<=m;i++){
        if(!q[i]){ // 主件
            for(int j=1;j<p[i];j++)h[j]=0;
            for(int j=p[i];j<=n;j++)
                h[j]=f[j-p[i]]+v[i]; // 此處 h 存放了購買目前主件可以獲得的值
            for(int j=1;j<=m;j++)
                if(q[j]==i) // 是目前主件的附件，是以相當于枚舉該主件的附件
                    for(int k=n;k>=p[i]+p[j];k--) // 01背包，h 已經買了目前主件
                        h[k]=max(h[k],h[k-p[j]]+v[j]); // 此處是再購買目前附件
            // 到這裡，h 存的是購買目前主件，然後對附件進行任意選擇後得到的最大值
            // 而原來的 f 中沒有購買目前主件
            for(int j=p[i];j<=n;j++)
                f[j]=max(f[j],h[j]); // 是以此處是對是否購買目前主件進行選擇
            // 總結：
            // 對于一個主件，首先用 01背包 選出來怎麼搭配附件的最優解，此處的前提都是購買主件
            // 然後再與不購買主件進行最優選擇
        }
    }
    printf("%d\n",f[n]);
    return 0;
}