POJ 2063 Investment：完全背包解決多年投資增值問題

問題描述

初始資金 V，year 年。每年有 n 種投資項目，項目 i 成本 c[i]（千元倍數），收益 w[i]。每年可重複投資同一項目（完全背包），年終本金加收益作為下一年本金。求最終資金。

關鍵建模：每年獨立完全背包

每年本金 V 固定，背包容量 cap = V / 1000（千元單位）。
項目：重量 c[i]、價值 w[i]，**可無限選取** → 完全背包。
年終最大收益 dp[cap]，新本金 V += dp[cap]。

完全背包標準寫法

for (int i = 0; i < n; i++)          // 遍歷物品
    for (int j = c[i]; j <= cap; j++) // 正序遍歷容量（關鍵！）
        dp[j] = max(dp[j], dp[j - c[i]] + w[i]);

正序遍歷容量體現「可重複選取」。

完整代碼

#include 
#include 
#include 
using namespace std;

int c[20], w[20], dp[100000];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int V, year, n;
        scanf("%d%d", &V, &year);
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &c[i], &w[i]);
            c[i] /= 1000; // 單位統一為千元
        }
        while (year--) {
            int cap = V / 1000;
            memset(dp, 0, sizeof(dp)); // 每年重置！
            for (int i = 0; i < n; i++)
                for (int j = c[i]; j <= cap; j++)
                    dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
            V += dp[cap];
        }
        printf("%d\n", V);
    }
    return 0;
}

易錯點提醒

1. 每年必須重置 dp 數組：`memset(dp, 0, sizeof(dp))` 放在 `while(year--)` 循環內
2. 單位統一：成本除以 1000，容量按千元計算
3. 完全背包正序遍歷：`j` 從 `c[i]` 到 `cap` 遞增
4. 結果類型：最終資金可能超過 `int`，但題目數據範圍 `int` 足夠

複雜度

• 每年：O(n × cap)，cap ≤ V/1000，V 增長但數據範圍可控
• 總時間：O(year × n × cap)
• 空間：O(cap)

總結

多年投資問題分解為**獨立的年度完全背包**。關鍵在於識別「每年決策獨立、項目可重複投資」的完全背包特徵，並正確處理單位換算與年度疊代。模板級完全背包寫法直接適用。