ACM 經典背包問題：動態規劃求解最大自習收益

問題背景

期末考試逼近，草灘小王子被迫去自習。除了自習，他還想到 n 件可做的事，每件事花費固定時間（最小單位 1 秒）且必須一次完成，做完後能永久提升（或降低）自習效率。初始效率為 1。小王子可在任意時刻開始自習任意時長，若當前效率為 k_i，自習 t_i 秒的收穫為 s_i = t_i × k_i。給定總時間 t 秒，如何分配時間以獲得最大自習收穫？

輸入格式

第一行整數 T (T ≤ 10) 表示測試組數。每組測試：第一行兩整數 t (0 ≤ t ≤ 1000), n (1 ≤ n ≤ 10000)。接下來 n 行，每行兩整數 a, b (0 ≤ a ≤ 100, 0 ≤ b ≤ 30)，分別代表第 i 件事所需時間與效率提升值。

輸出格式

對每組測試輸出一行，即草灘小王子能獲得的最大收穫。

範例

輸入
1
20 3
10 5
6 2
5 4

輸出
75

提示： 小王子花 5 秒完成第 3 件事（效率 +4），然後用剩餘 15 秒自習，收穫 = 15 × (1+4) = 75。

解題思路：動態規劃

這是一個典型的 0-1 背包問題 變體。狀態定義：dp[i][j] 表示前 i 件事中選擇若干件，總耗時為 j 秒時的最大效率提升總和。由於效率提升是累加的，最終收穫 = (總時間 - 總任務耗時) × (1 + 總效率提升)。我們可以先用 DP 求出每種可能的總耗時對應的最大效率提升，再枚舉總耗時計算最大收穫。

狀態轉移方程

dp[j] = max(dp[j], dp[j - a_i] + b_i)   // 逆序遍歷 j 從 t 到 a_i

其中 dp[j] 為耗時 j 秒可獲得的最大效率增益。初始 dp[0] = 0，其餘 -∞。

計算最大收穫

遍歷所有可能的總耗時 j (0 ≤ j ≤ t)，收穫 = (t - j) × (1 + dp[j])，取最大值。

複雜度分析

• 時間複雜度：O(T × n × t) ，n ≤ 10000, t ≤ 1000，最壞約 10^7 操作，可行。
• 空間複雜度：O(t) ，一維 DP 數組即可。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int t, n; cin >> t >> n;
        vector dp(t + 1, -INF);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            int a, b; cin >> a >> b;
            for (int j = t; j >= a; --j) {
                if (dp[j - a] != -INF)
                    dp[j] = max(dp[j], dp[j - a] + b);
            }
        }
        long long ans = 0;
        for (int j = 0; j <= t; ++j) {
            if (dp[j] != -INF) {
                long long gain = 1LL * (t - j) * (1 + dp[j]);
                ans = max(ans, gain);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

總結

本題核心在於將「先做任務提升效率，再自習」轉化為背包問題：選擇任務子集，使 (剩餘時間) × (1 + 總效率增益) 最大。一維 DP 逆序優化空間，枚舉耗時求最優解。