AcWing487. 金明的預算方案題解（DP，分組背包）

文章目錄

• 題目描述
• 題解 (DP,分組背包問題)
• 時間複雜度
• C++代碼

題目描述

題目描述
如果要買歸類為附件的物品，必須先買該附件所屬的主件。

每個主件可以有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]（其中*為乘号）

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

輸入樣例

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

輸出樣例
2200
           

題解 (DP,分組背包問題)

可以将每個主件及其附件看作一個物品組，記主件為 pp，兩個附件為 a,ba,b，則最多一共有4種組合：

p 
p,a 
p,b 
p,a,b 
           

這四種組合是互斥的，最多隻能從中選一種，是以可以将每種組合看作一個物品，那麼問題就變成了分組背包問題。可以參考AcWing 9. 分組背包問題。

在枚舉四種組合時可以使用二進制的思想，可以簡化代碼。

時間複雜度

分組背包的時間複雜度是 物品總數 * 總體積，是以總時間複雜度是 O(Nm)O(Nm)。

C++代碼

#include <iostream>
#include <vector>

using namespace std;
const int N = 70, M = 32010;
int n, m;
typedef pair<int, int> PII;
PII master[N];
vector<PII> sv[N];
int f[M];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) master[i] = {v, v * w};
        else sv[q].push_back({v, v * w});
    }
    for (int i = 1; i <= n; i++) {
        if (master[i].first) {
            for (int j = m; ~j; j--) {
                for (int k = 0; k < 1 << sv[i].size(); k++) {
                    int v = master[i].first, w = master[i].second;
                    for (int u = 0; u < sv[i].size(); u++) {
                        if (k >> u & 1) {
                            v += sv[i][u].first;
                            w += sv[i][u].second;
                        }
                    }
                    if (j >= v)
                        f[j] = max(f[j], f[j - v] + w);
                }
            }
        }
    }
    cout << f[m] << endl;

    return 0;
}