P1064 [NOIP2006 提高組] 金明的預算方案

題意：

每個物品有價格和價值，物品之間存在依賴關系（單向的），現在又n元錢，買哪些物品，即滿足依賴關系又使得每件物品的價格與價值的乘積的總和最大
（每個主件最多兩個附件）

題解：

方法一：
學習博客
因為每個主件最多兩個附件，且附件必須依賴于主件，所以對每個主件一共就五種決策：
1.不選，然后考慮下一個
2.選擇且只選主件
3.選擇這個主件，且選擇附件1
4.選擇這個主件，且選擇附件2
5.選擇這個主件，且選擇附件1，2
我們設變量fv[i][j]表示主件為i的第j個附件的價值與重量乘積
fw[i][j]表示主件為i的第j個附件的重量
dp[i]就是01背包中的設定
我們仿照01背包對上面5種情況列出轉移方程

//情況1：只要主件 和啥都不要比較 dp[j]=max(dp[j],dp[j-mw[i]]+mv[i]); //情況2：主件和附件1 和上面選出的較大值比較 if(j>=mw[i]+fw[i][1])dp[j]=max(dp[j],dp[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]); //情況3：主件和附件2 和上面選出的較大值比較 if(j>=mw[i]+fw[i][2])dp[j]=max(dp[j],dp[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]); //情況4：都要 if(j>=mw[i]+fw[i][1]+fw[i][2]) dp[j]=max(dp[j],dp[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]);

方法2：
學習文章
根據依賴關系我們可以得知這是一個樹型結構，這個樹的特點：
一個物品所依賴的所有物品都是他的父節點
如果一個物品不選,對應到樹上,他所有的子節點都不能選
現在我們如何用01背包來解決這個樹形問題
我們可以將樹轉化成鏈，通過dfs序實現
對樹求后序遍歷，后序遍歷的順序是前后中，也就是一個節點的兒子和左兄弟都在他前面
這樣我們可以有以下決策:
1.選當前物品，狀態i由i-1（從兒子）轉移而來
2.不選擇，這個點的兒子也不能選，那狀態只能從前面最近的左兄弟轉移
pre[u]表示編號為u的左兄弟的編號
dp[i][j]=max(dp[pre[i]][j],dp[i-1][j-v]+w)
總復雜度為O(n+nm),關鍵是這個方法可以解決附件上有附加的情況，能處理情況更廣
不過我對這個方法還不是完全理解。。有待消化

代碼：

#include<iostream> using namespace std; int m,n,mw[33333],mv[33333],fw[33333][3],fv[33333][3],dp[33333],v,p,q; //mw主件重量，mv主件價值，fw主件對應的附件重量，fv主副價值，n總重量，m總個數 int main() { cin>>n>>m; for(int i=1;i<=m;i++){ cin>>v>>p>>q; if(!q){//如果是主件 mw[i]=v;//主件重量 mv[i]=v*p;//主件價值與重量乘積 } else{//如果是附件 fw[q][0]++;//記錄主件的附件個數（只記錄在fw就行，fv那里沒用 fw[q][fw[q][0]]=v;//主件的個數是用來確定該附件應該填在第一個還是第二個格子里 fv[q][fw[q][0]]=v*p;//（是第一個還是第二個附件） } } for(int i=1;i<=m;i++) for(int j=n;j>=mw[i];j--){//01背包模板 //每一個if的前提是背包能不能裝下該物品 //情況1：只要主件 和啥都不要比較 dp[j]=max(dp[j],dp[j-mw[i]]+mv[i]); //情況2：主件和附件1 和上面選出的較大值比較 if(j>=mw[i]+fw[i][1])dp[j]=max(dp[j],dp[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]); //情況3：主件和附件2 和上面選出的較大值比較 if(j>=mw[i]+fw[i][2])dp[j]=max(dp[j],dp[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]); //情況4：都要 if(j>=mw[i]+fw[i][1]+fw[i][2]) dp[j]=max(dp[j],dp[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]); } //輸出在價值為n時能得到的最大值 cout<<dp[n]<<endl; return 0; } #include <cstdio> #include <algorithm> using namespace std; const int maxn = 64; const int maxm = maxn; const int maxv = 33333; struct Node{//表示物品int v,w;Node() = default;Node(int a,int b):v(a),w(b){} }d[maxn],t[maxn]; struct Edge{int from,to;Edge() = default;Edge(int a,int b):from(a),to(b){} }Edges[maxm]; int head[maxn],nxt[maxm],root[maxn],rp; inline void addedge(int from,int to){static int tot;Edges[++tot] = Edge(from,to);nxt[tot] = head[from];head[from] = tot; } int pre[maxn],f[maxn][maxv],p = 0; void dfs(int u){int tp = p;//由于后序遍歷的性質,一個點的左兄弟顯然是進入這個點時序列中的最后一個點for(int i = head[u];i;i = nxt[i]){Edge &e = Edges[i];dfs(e.to);}d[++p] = t[u];//后序遍歷pre[p] = tp;//求左兄弟,注意,pre[t]表示序列中編號為t的節點的左兄弟的編號 } int n,m; int main(){scanf("%d %d",&m,&n);for(int i = 1;i <= n;i++){//建圖int v,w,faz;scanf("%d %d %d",&v,&w,&faz);t[i] = Node(v,v * w);//先預處理它的權值addedge(faz,i);//有個技巧,如果一個點是主件,我們就認為它依賴于虛擬點0}dfs(0);for(int i = 1;i <= n;i++)//dp求解for(int j = 0;j <= m;j++)if(j >= d[i].v)f[i][j] = max(f[pre[i]][j],f[i - 1][j - d[i].v] + d[i].w);else f[i][j] = f[pre[i]][j];//轉移 printf("%d\n",f[n][m]);return 0; }

總結

以上是生活随笔為你收集整理的P1064 [NOIP2006 提高组] 金明的预算方案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。