UVA 10130 SuperSale：多重 01 背包（每人獨立）

問題描述

有 n 件物品，每件有價值 v 和重量 w。有 m 個人，每人最大負重 W_i。每人可選物品互不影響（物品無限供應）。求所有人能帶走的最大總價值。

解題思路

每人獨立是一個 01 背包問題（每件物品每人最多拿一件，但不同人可拿同一物品）。對每個人，容量為 W_i，跑 01 背包得最大價值，累加即可。由於 W_i ≤ 1000（題目隱含），n ≤ 1000，m ≤ 100，O(m * n * W) 可接受。

代碼實現 (C++)

#include 
using namespace std;
struct Item { int v, w; };
int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector items(n);
        for (int i = 0; i < n; ++i) cin >> items[i].v >> items[i].w;
        int m; cin >> m;
        vector cap(m);
        for (int i = 0; i < m; ++i) cin >> cap[i];
        long long total = 0;
        for (int c : cap) {
            vector dp(c+1, 0);
            for (auto &it : items) {
                for (int j = c; j >= it.w; --j)
                    dp[j] = max(dp[j], dp[j - it.w] + it.v);
            }
            total += dp[c];
        }
        cout << total << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(T * m * n * W_max)。
• 空間複雜度：O(W_max)。

總結

多組獨立 01 背包，利用物品可重複被不同人選擇的特性，逐人求解累加。注意背包循環順序（倒序）保證 01 特性。