地址：https://www.cnblogs.com/FReQuenter5156/p/shuxingyilaidp.html/
簡介這類背包本質(zhì)上是分組背包問題。
(資料圖片僅供參考)
將一個節(jié)點的每一棵子樹看作一組，進(jìn)行分組背包。所謂分組背包，即在選擇物品的時候，一開始將物品分為好幾組，在選擇時，可以從每一組中至多選擇一件物品，問如何獲得最大的價值，所以我們每次可以枚舉這個組數(shù)，用 \(i\) 表示第幾組，用 \(j\) 表示體積，用 \(k\) 來表示選擇的物品，偽代碼如下：
for (int i=0到組數(shù))for (int j=max_v到0)for (int k=此組所有物品)f[j]=max(f[j],f[j-v[k]]+w[k])注意循環(huán)順序。這個和 01 背包的道理類似。
例題[CTSC1997] 選課題面在大學(xué)里每個學(xué)生，為了達(dá)到一定的學(xué)分，必須從很多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)?，F(xiàn)在有 \(N\) 門功課，每門課有個學(xué)分，每門課有一門或沒有直接先修課（若課程 a 是課程 b 的先修課即只有學(xué)完了課程 a，才能學(xué)習(xí)課程 b）。一個學(xué)生要從這些課程里選擇 \(M\) 門課程學(xué)習(xí)，問他能獲得的最大學(xué)分是多少？
題解定義\(f_{i,j}\) 表示當(dāng)前第 \(i\) 個點的子樹內(nèi)選 \(j\) 個點（不包括自己）的最大學(xué)分。
轉(zhuǎn)移直接套板子。初值在輸入時已經(jīng)設(shè)置好了，DP 中只要比大小。具體參考代碼。
代碼#include#define MAXN 305using namespace std;int n,m,k[MAXN],s[MAXN],sz[MAXN],f[MAXN][MAXN];vector gv[MAXN];void dfs(int now,int father){sz[now]=1;for(auto nx:gv[now]){if(nx!=father) dfs(nx,now),sz[now]+=sz[nx];}}void dp(int now,int father){int sum=0;for(auto nx:gv[now]){if(nx==father) continue;sum+=sz[nx];dp(nx,now);for(int j=sum;j>=0;j--){for(int k=0;k=1){f[now][j]=max(f[now][j],f[now][j-k-1]+f[nx][k]);}}}}}signed main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>k[i]>>s[i];gv[k[i]].push_back(i);f[i][0]=s[i];}dfs(0,0);dp(0,0);cout< 某收費(fèi)有線電視網(wǎng)計劃轉(zhuǎn)播一場重要的足球比賽。他們的轉(zhuǎn)播網(wǎng)和用戶終端構(gòu)成一棵樹狀結(jié)構(gòu)，這棵樹的根結(jié)點位于足球比賽的現(xiàn)場，樹葉為各個用戶終端，其他中轉(zhuǎn)站為該樹的內(nèi)部節(jié)點。
從轉(zhuǎn)播站到轉(zhuǎn)播站以及從轉(zhuǎn)播站到所有用戶終端的信號傳輸費(fèi)用都是已知的，一場轉(zhuǎn)播的總費(fèi)用等于傳輸信號的費(fèi)用總和。
現(xiàn)在每個用戶都準(zhǔn)備了一筆費(fèi)用想觀看這場精彩的足球比賽，有線電視網(wǎng)有權(quán)決定給哪些用戶提供信號而不給哪些用戶提供信號。
寫一個程序找出一個方案使得有線電視網(wǎng)在不虧本的情況下使觀看轉(zhuǎn)播的用戶盡可能多。
題解定義\(f_{i,j}\) 表示到第 \(i\) 個點供應(yīng) \(j\) 個用戶的最大收益。最后求答案的時候枚舉下 \(f_{1,i}\geq 0\) 的最大 \(i\)。注意初值賦 -INF。
轉(zhuǎn)移也是套板子。直接看代碼應(yīng)該就能理解。
代碼#include#define fi first#define se second#define MAXN 3005using namespace std;vector> gv[MAXN];int n,m,f[MAXN][MAXN],v[MAXN];int dp(int now){if(now>=n-m+1){f[now][1]=v[now];return 1;}int sum=0;for(auto nx:gv[now]){int tmp=dp(nx.fi);sum+=tmp;for(int j=sum;j>=1;j--){for(int k=1;k<=tmp;k++){if(j-k>=0) f[now][j]=max(f[now][j],f[now][j-k]+f[nx.fi][k]-nx.se);}}}return sum;}signed main(){memset(f,-0x3f,sizeof(f));cin>>n>>m;for(int i=1;i<=n-m;i++){int k;cin>>k;for(int j=1;j<=k;j++){int a,c;cin>>a>>c;gv[i].push_back({a,c});}} for(int i=n-m+1;i<=n;i++) cin>>v[i];for(int i=1;i<=n;i++) f[i][0]=0;int maxn=0;dp(1);for(int i=0;i<=m;i++) if(f[1][i]>=0) maxn=i;cout< 一場可怕的地震后，人們用 \(N\) 個牲口棚（編號 \(1\sim N\)）重建了農(nóng)夫 John 的牧場。由于人們沒有時間建設(shè)多余的道路，所以現(xiàn)在從一個牲口棚到另一個牲口棚的道路是惟一的。因此，牧場運(yùn)輸系統(tǒng)可以被構(gòu)建成一棵樹。
John 想要知道另一次地震會造成多嚴(yán)重的破壞。有些道路一旦被毀壞，就會使一棵含有 \(P\) 個牲口棚的子樹和剩余的牲口棚分離，John 想知道這些道路的最小數(shù)目。
題解定義\(f_{i,j}\) 表示當(dāng)前第 \(i\) 個點為根的子樹保留 \(j\) 個點（包括自己）刪去的最小的邊數(shù)。答案需要枚舉所有的子樹。
轉(zhuǎn)移其實也差不多。可以直接看代碼。注意初始值 \(f_{i,1}\) 為每個點的出度。這題相對來說比較細(xì)節(jié)。如方程中的 -1，和自己的“父親”的連邊不能拆。
#includeusing namespace std;vector gv[155];int n,p,ans=0x3f3f3f3f,f[155][155],sz[155],od[155];bool ir[155];void dp(int now){ sz[now]=1; if(!od[now]) return f[now][1]=0,void(); for(auto nx:gv[now]){ dp(nx); sz[now]+=sz[nx]; for(int j=sz[now];j>=0;j--) for(int k=1;k>n>>p; for(int i=1;i>x>>y; gv[x].push_back(y),od[x]++,ir[y]=true; } memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++) f[i][1]=od[i]; int root=0; for(int i=1;i<=n;i++) if(!ir[i]) root=i; dp(root); for(int i=1;i<=n;i++){ if(i==root) ans=min(ans,f[i][p]); else ans=min(ans,f[i][p]+1);} cout< JSOI 信息學(xué)代表隊一共有 \(N\) 名候選人，這些候選人從 \(1\) 到 \(N\) 編號。方便起見，JYY 的編號是 \(0\) 號。每個候選人都由一位編號比他小的候選人\(R_i\) 推薦。如果 \(R_i = 0\)?，則說明這個候選人是 JYY 自己看上的。
為了保證團(tuán)隊的和諧，JYY 需要保證，如果招募了候選人 \(i\)，那么候選人 \(R_i\) 也一定需要在團(tuán)隊中。當(dāng)然了，JYY 自己總是在團(tuán)隊里的。每一個候選人都有一個戰(zhàn)斗值 \(P_i\) ，也有一個招募費(fèi)用 \(S_i\) 。JYY 希望招募 \(K\) 個候選人（JYY 自己不算），組成一個性價比最高的團(tuán)隊。也就是，這 \(K\) 個被 JYY 選擇的候選人的總戰(zhàn)斗值與總招募費(fèi)用的比值最大。
題解簡單說一下。比值類似于 最優(yōu)比例生成樹，可以使用分?jǐn)?shù)規(guī)劃，然后就可以去套板子了。
沒來得及實現(xiàn)，可以參考洛谷題解。
