HDU 2191 珍惜現在，感恩生活：多重背包問題

題目背景

紀念汶川大地震。有 n 元資金，m 種大米，每種有價格 p、重量 h、袋數 c。只能整袋購買，求最大購買重量。資金可不花完。多組測試資料。

模型轉化：多重背包

• 背包容量：n (資金)
• 物品：每種大米第 i 種有 c[i] 件，體積 p[i]，價值 h[i]。
• 目標：最大化總價值 (重量)。

解法：二進制優化 / 單調隊列 / 直接多重背包

資料範圍：n ≤ 100, m ≤ 100, c ≤ 20。總物品數 ≤ 2000，容量 100。直接 **O(n * Σc)** 多重背包即可 (約 2e5 操作)，無需優化。

狀態定義與轉移

dp[j]：花費恰好 j 元能買到的最大重量。
初始化：dp[0..n] = 0。
對每種大米 i，執行 c[i] 次 01 背包更新 (或直接三重迴圈)：

for (int i = 1; i <= m; ++i)
    for (int k = 1; k <= c[i]; ++k) // 第 k 袋
        for (int j = n; j >= p[i]; --j) // 逆序保證 01 性質
            dp[j] = max(dp[j], dp[j - p[i]] + h[i]);

答案：max(dp[0..n]) (資金可不花完)。

完整代碼

#include 
#include 
using namespace std;
const int M = 105;
int dp[M];
int main() {
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> m >> n; // 注意輸入順序：m 種類, n 資金
        int p[M], h[M], c[M];
        for (int i = 1; i <= m; ++i) cin >> p[i] >> h[i] >> c[i];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= m; ++i)
            for (int k = 1; k <= c[i]; ++k)
                for (int j = n; j >= p[i]; --j)
                    dp[j] = max(dp[j], dp[j - p[i]] + h[i]);
        int ans = 0;
        for (int j = 0; j <= n; ++j) ans = max(ans, dp[j]);
        cout << ans << endl;
    }
    return 0;
}

測試樣例

輸入：
1
8 2
2 100 4
4 100 2
輸出：400
解析：8 元可買 4 袋第一種 (2*4=8 元, 100*4=400 公斤)，或 2 袋第二種 (200 公斤)，最大 400。

複雜度

• 時間：O(T * n * Σc) ≤ 100 * 100 * 2000 = 2e7，極快。
• 空間：O(n) = 100。