背包問題：購物單
題目描述
王強今天很開心，公司發(fā)給N元的年終獎。王強決定把年終獎用于購物，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：
| 主件 | 附件 |
| 電腦 | 打印機，掃描儀 |
| 書柜 | 圖書 |
| 書桌 | 臺燈，文具 |
| 工作椅 | 無 |
如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有 0 個、 1 個或 2 個附件。附件不再有從屬于自己的附件。王強想買的東西很多，為了不超出預(yù)算，他把每件物品規(guī)定了一個重要度，分為 5 等：用整數(shù) 1 ~ 5 表示，第 5 等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是 10 元的整數(shù)倍）。他希望在不超過 N 元（可以等于 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設(shè)第 j 件物品的價格為 v[j] ，重要度為 w[j] ，共選中了 k 件物品，編號依次為 j 1 ， j 2 ，……， j k ，則所求的總和為：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 為乘號）
請你幫助王強設(shè)計一個滿足要求的購物單。
輸入描述:
輸入的第 1 行，為兩個正整數(shù)，用一個空格隔開：N m
（其中 N （ <32000 ）表示總錢數(shù)， m （ <60 ）為希望購買物品的個數(shù)。）
從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數(shù)據(jù)，每行有 3 個非負(fù)整數(shù) v p q
（其中 v 表示該物品的價格（ v<10000 ）， p 表示該物品的重要度（ 1 ~ 5 ）， q 表示該物品是主件還是附件。如果 q=0 ，表示該物品為主件，如果 q>0 ，表示該物品為附件， q 是所屬主件的編號）
輸出描述:
輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（ <200000 ）。
示例1
輸入
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
輸出
2200
思路
把（每個主件與其相應(yīng)附件的集合）的（所有包含主件的子集）歸到一個組中，組的個數(shù)就是主件的個數(shù)。然后每組中只選一個子集，這樣就轉(zhuǎn)化為了分組背包問題，代碼如下所示：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int N_size = 32001, m_size = 61; 5 int N, m, v[m_size], p[m_size], q, f[N_size]; //f[i]為最大價格為i時，所有被選物品的價格、重要度之積的和 6 int group[m_size][3]; //group[][0]為主件，group[][1]和group[][2]為兩個附件 7 int main() { 8 cin >> N >> m; 9 for (int i = 1; i <= m; ++i) { 10 cin >> v[i] >> p[i] >> q; 11 if (q == 0) 12 group[i][0] = 1; //如果第i件物品是主件，將group[i][0]置1 13 //如果第i件物品是附件 14 else if (group[q][2] == 0)//如果兩個附件位都未使用，將第二個附件位置為i 15 group[q][2] = i; 16 else //如果第二個附件位已使用，將第一個附件位置為i 17 group[q][1] = i; 18 } 19 for (int i = 1; i <= m; ++i) { 20 if (group[i][0] == 0) //若不是主件直接跳過 21 continue; 22 //轉(zhuǎn)化為分組背包問題，每組有s種選擇 23 int s = (group[i][1] == 0 ? 1 : 2) * (group[i][2] == 0 ? 1 : 2); 24 for (int j = N; j >= 0; --j) { 25 for (int k = 0; k < s; ++k) { 26 int vk = v[i] + v[group[i][1]] * ((k & 2) >> 1) + v[group[i][2]] * (k & 1); //每種選擇物品所占體積 27 if (j >= vk) { 28 int wk = v[i] * p[i] + v[group[i][1]] * p[group[i][1]] * ((k & 2) >> 1) + v[group[i][2]] * p[group[i][2]] * (k & 1); //每種選擇物品價格、重要度之積的和 29 f[j] = max(f[j], f[j - vk] + wk); 30 } 31 } 32 } 33 } 34 cout << f[N]; 35 }
浙公網(wǎng)安備 33010602011771號