題目描述
金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：

主件 附件

電腦 打印機，掃描儀

書柜 圖書

書桌 臺燈，文具

工作椅 無

如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。于是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是10元的整數倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：

v[j1]w[j1]+v[j2]w[j2]+ …+v[jk]w[jk]。（其中為乘號）

請你幫助金明設計一個滿足要求的購物單。

輸入輸出格式
輸入格式：
輸入的第1行，為兩個正整數，用一個空格隔開：

N m （其中N（<32000）表示總錢數，m（<60）為希望購買物品的個數。）

從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有3個非負整數

v p q （其中v表示該物品的價格（v<10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。如果q=0，表示該物品為主件，如果q>0，表示該物品為附件，q是所屬主件的編號）

輸出格式：
輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<200000）。

輸入輸出樣例
輸入樣例#1：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
輸出樣例#1：
2200
說明
NOIP 2006 提高組 第二題

【分析】：
基本思路
這是一個 有依賴(?) 的01背包

既然物品分為主件和附件兩類，且每個主件最多包含兩個附件，那么我們不妨枚舉所有的主件。那么，對于每次枚舉，會有五種情況：

什么都不買
只買主件
買主件和第一個附件
買主件和第二個附件
買主件和兩個附件
只要把這四種情況最終的價值算出來，取最大值就可以了。

#include <iostream> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int maxn = 32005; const int N = 105; #define ll long longint n, m; int a, b, c; int v[N],q[N],p[N], v1[N],q1[N],v2[N],q2[N],dp[maxn];int main() {while(cin >> n >> m){for(int i=1; i<=m; i++){cin >> a >> b >> c;if(c==0){v[i]=a; q[i]=b;}else{if(q1[c]==0){v1[c]=a;q1[c]=b;}else{v2[c]=a; q2[c]=b;}}}for(int i=1; i<=m; i++){for(int j=n; j>=v[i]; j--){if(j-v[i]>=0){dp[j]=max(dp[j], dp[j-v[i]] + v[i]*q[i]);}if(j-v[i]-v1[i]>=0){dp[j]=max(dp[j], dp[j-v[i]-v1[i]] + v[i]*q[i] + v1[i]*q1[i]);}if(j-v[i]-v2[i]>=0){dp[j]=max(dp[j], dp[j-v[i]-v2[i]] + v[i]*q[i] + v2[i]*q2[i]);}if(j-v[i]-v1[i]-v2[i]>=0){dp[j]=max(dp[j], dp[j-v[i]-v1[i]-v2[i]] + v[i]*q[i] + v1[i]*q1[i] + v2[i]*q2[i]);}}}cout<<dp[n]<<endl;} } 此題是01背包問題的變形。物品的重要度乘以價格是背包問題中的價值，物品的價格是背包問題中的體積。1、我們可以把如何在眾多主件與附件之中選擇購買的問題轉變為看成購買的5種方案：（1）什么都不買，（2）只買主件，（3）買主件和附件1，（4）買主件和附件2，（5）買主件和兩個附件。2、有些主件有附件，而有些沒有，這為我們思考帶來了負擔，我們完全可以假設任何主件都有兩個附件，也就是說如果題目沒有給出某個主件的附件的話，我們就假設這個主件的附件是存在的，且價格和重要度都等于0。這個假設首先不會影響到程序的正確性，也不會增加多少運算時間，且這種假設使得我們想問題和寫程序都變得簡單多了。3、題目中的價格都是10的這個條件，可以減少一些時間和空間的開銷。此題和01背包問題有2個主要的區別：區別一：01背包問題對當前物品考慮的只有買和不買兩種情況，而此題需要考慮上面所說的5種不同的購買方案。區別二：01背包問題是用v[i]來保存第i個物品的價值，而此題需要用v[i]來保存第i個物品和它的兩個附件的價值，此時我們需要二維數組來實現，物品體積w同樣需要用二維數組來保存。v[i][0]表示第i個物品的主件價值， v[i][1]表示第i個物品的第一個附件的價值，v[i][2]表示第i個物品的第二個附件的價值 .w[i][0..2]表示同樣的物品的體積。f[i,j]表示給定i個物品和j的空間能夠獲得的最大價值總合。則： f[i,j]=max{f[i-1,j],f[i-1,j-w[i,0]]+v[i,0],f[i-1,j-w[i,0]-w[i,1]]+v[i,0]+v[i,1],f[i-1,j-w[i,0]-w[i,2]]+v[i,0]+v[i,2],f[i-1,j-w[i,0]-w[i,1]-w[i,2]]+v[i,0]+v[i,1]+v[i,2]} 其實，此題還有一個關鍵點，就是輸入數據的處理。 根據題目的意思，q是物品的編號，但是這個編號是在考慮附件時統計的編號，而我們認為附件和主件是一體的，因此附件編號因該和主件一致，所以我們需要對題目給出的編號進行轉換。 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm>using namespace std; const int maxn = 40000; int f[70][maxn]; int value[70][3],imp[70][3]; int main() { int n,m; int v,p,q; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { scanf("%d%d%d",&v,&p,&q); //為主件 if (!q) { value[i][0] = v; imp[i][0] = p; } //為附件 else { if (!value[q][1]) { value[q][1] = v; imp[q][1] = p; } else { value[q][2] = v; imp[q][2] = p; } } } memset(f,0,sizeof(f)); for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { if (j-value[i][0]>=0) { //僅主件 f[i][j] = max(f[i-1][j],f[i-1][j-value[i][0]] + value[i][0]*imp[i][0]); //這個時候的f[i][j]表示僅有主件的時候的情況，而下面每種加附件的情況，都是在有主件的基礎下，所以 //直接和f[i][j]比較 //主件 + 附件1 if (j-value[i][0]-value[i][1]>=0) f[i][j] = max(f[i][j],f[i-1][j-value[i][0]-value[i][1]] + value[i][0]*imp[i][0] + value[i][1]*imp[i][1]); //主件 + 附件2 if (j-value[i][0]-value[i][2]>=0) f[i][j] = max(f[i][j],f[i-1][j-value[i][0]-value[i][2]] + value[i][0]*imp[i][0] + value[i][2]*imp[i][2]); //主件 + 所有附件 if (j-value[i][0]-value[i][1]-value[i][2]>=0) f[i][j] = max(f[i][j],f[i-1][j-value[i][0]-value[i][1]-value[i][2]] + value[i][0]*imp[i][0] + value[i][1]*imp[i][1] + value[i][2]*imp[i][2]); } else f[i][j] = f[i-1][j]; } } printf("%d\n",f[m][n]); return 0; } P.S:一開始有個assembler messages的錯誤，糾結的半天，原來是一開始弄的f[maxn][maxn]數組太大爆炸了，

轉載于:https://www.cnblogs.com/Roni-i/p/9004691.html

總結

以上是生活随笔為你收集整理的洛谷 P1064 金明的预算方案【有依赖的分组背包】的全部內容，希望文章能夠幫你解決所遇到的問題。

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