1. 問題描述：

金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說："你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過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表示總錢數，m為希望購買物品的個數。從第2行到第m+1行，第j行給出了編號為j - 1的物品的基本數據，每行有3個非負整數v p q，其中v表示該物品的價格，p表示該物品的重要度（1~5），q表示該物品是主件還是附件。
如果q = 0，表示該物品為主件，如果q > 0，表示該物品為附件，q是所屬主件的編號。?

輸出格式

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

數據范圍

N < 32000，m < 60，v < 10000

輸入樣例：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

輸出樣例：

2200
來源：https://www.acwing.com/problem/content/description/489/

2. 思路分析：

分析題目可以知道這道題目屬于分組背包問題一個擴展，我們可以將每一個主件與對應的附件看成一組，在每一組中可以選擇主件與若干個附件（選擇了某個組中的附件之后一定要選擇主件），我們需要求解的是在不超過總金額N的前提下選擇的所有物品中物品的價格與重要度乘積的總和的最大值，類似于分組背包問題，我們可以嘗試每一組中所有可能的選擇方案來更新對應金額能夠獲得的總價值。其中需要聲明一個二維數組或者列表，其中dp[i][j]表示前i組物品中總金額不超過j的前提下能夠獲得的最大價值，可以發現在狀態計算的時候我們使用的只是上一個狀態的值所以我們可以將二維數組優化為一維數組，其中dp[i]表示總金額不超過i的前提下能夠獲得的最大價值；狀態計算的時候需要使用四層循環進行枚舉，第一層循環枚舉所有的物品組，每一個組中對應主件和附件，第二層循環枚舉總金額（相當于枚舉的是體積），因為使用的是一維數組而且在狀態計算的時候使用的是上一個狀態的值所以需要逆序遍歷體積，第三層循環枚舉所有可能的選擇方案，需要枚舉1 << len(servent[i])，表示附件數量為len(servent[i])所有的選擇情況，每一個數字對應的二進制中對應的0和1表示對應位置附件是否選擇，枚舉所有的選擇方案來更新對應的dp數組對應金額的值即可，最終的dp[N]就是我們要求解的答案。

3. 代碼如下：

python：

if __name__ == '__main__':# 分組背包問題擴展, m表示總錢數, n表示物品的個數m, n = map(int, input().split())# 存儲主件對應的價格和對應的權重master = [list() for i in range(n + 1)]# 存儲附件編號servent = [list() for i in range(n + 1)]# 先存儲對應的主件與附件中對應的編號for i in range(1, n + 1):v, p, q = map(int, input().split())if q > 0:# 附件servent[q].append([v, v * p])else:master[i].append([v, v * p])dp = [0] * (m + 1)for i in range(1, n + 1):# 因為使用到的是上一次的狀態所以優化為一維之后需要逆序枚舉體積for j in range(m, -1, -1):# 二進制枚舉, 枚舉所有可能的選擇情況, 例如附件數目為2那么可能的選擇情況為2 ^ n所以枚舉這些數字對應位置是否為1來選擇對應的物品for k in range(1 << len(servent[i])):v, w = 0, 0if len(master[i]) > 0:v += master[i][0][0]w += master[i][0][1]for u in range(len(servent[i])):# 判斷當前這一位是否是1, 右移然后與1相與即可判斷當前的第u位是否是1if k >> u & 1:v += servent[i][u][0]w += servent[i][u][1]if j >= v:dp[j] = max(dp[j], dp[j - v] + w)print(dp[m])

c++：

#include <cstring> #include <iostream> #include <algorithm> #include <vector> #define v first #define w second using namespace std; typedef pair<int, int> PII;const int N = 60, M = 32010;int n, m; PII master[N]; vector<PII> servent[N]; int f[M];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++ ){int v, p, q;cin >> v >> p >> q;p *= v;if (!q) master[i] = {v, p};else servent[q].push_back({v, p});}for (int i = 1; i <= n; i ++ )for (int u = m; u >= 0; u -- ){for (int j = 0; j < 1 << servent[i].size(); j ++ ){int v = master[i].v, w = master[i].w;for (int k = 0; k < servent[i].size(); k ++ )if (j >> k & 1){v += servent[i][k].v;w += servent[i][k].w;}if (u >= v) f[u] = max(f[u], f[u - v] + w);}}cout << f[m] << endl;return 0; }

總結

以上是生活随笔為你收集整理的487 金明的预算方案（分组背包问题扩展）的全部內容，希望文章能夠幫你解決所遇到的問題。

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