HDU 3496 Watch The Movie：二維 01 背包 + 恰裝滿一維求最大價值

問題描述

DuoDuo 有 N 部想看的電影（N ≤ 100），每部有時長 Tᵢ 和喜愛值 Vᵢ。爺爺允許看 L 分鐘（L ≤ 1000）。商店**恰好賣 M 部**（M ≤ N）。選 M 部電影，總時長 ≤ L，最大化總喜愛值。若無法恰好看完 M 部輸出 0。

模型：二維 01 背包

• 狀態：`dp[i][j]` = 選前 k 部電影中選 **恰好 i 部**，總時長 **恰好 j** 的最大價值。
• 初始化：`dp[0][0] = 0`，其餘 `-INF`（不可達）。
• 轉移：對每部電影 (t, v)，逆序更新：
  `dp[i][j] = max(dp[i][j], dp[i-1][j-t] + v)` for `i=M..1, j=L..t`。
• 答案：`max(dp[M][j])` for `j=0..L`（因為總時長 ≤ L，不必恰好裝滿 L）。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = -0x3f3f3f3f;
const int MAXN = 105;
const int MAXL = 1005;
int dp[MAXN][MAXL];
int T[MAXN], V[MAXN];

int main() {
    int cas; scanf("%d", &cas);
    while (cas--) {
        int N, M, L; scanf("%d%d%d", &N, &M, &L);
        for (int i = 0; i < N; i++) scanf("%d%d", &T[i], &V[i]);

        for (int i = 0; i <= M; i++)
            for (int j = 0; j <= L; j++)
                dp[i][j] = INF;
        dp[0][0] = 0;

        for (int k = 0; k < N; k++) {
            for (int i = M; i >= 1; i--) {
                for (int j = L; j >= T[k]; j--) {
                    if (dp[i-1][j-T[k]] != INF)
                        dp[i][j] = max(dp[i][j], dp[i-1][j-T[k]] + V[k]);
                }
            }
        }

        int ans = 0;
        for (int j = 0; j <= L; j++)
            ans = max(ans, dp[M][j]);
        if (ans > 0) printf("%d\n", ans);
        else printf("0\n");
    }
    return 0;
}

關鍵細節

複雜度

• 時間：O(N × M × L) = 100 × 100 × 1000 = 10⁷，極快。
• 空間：O(M × L) = 10⁵ int ≈ 0.4 MB，可滾動數組優化至 O(L)。

總結

HDU 3496 是**二維 01 背包 + 恰裝滿一維**的標準模板題。關鍵在於：狀態定義包含「選擇數量」，初始化用 `-INF` 標記不可達，轉移逆序，最後在容量上界內取最大值而非要求恰好裝滿。同類題見 POJ 1014、HDU 2602 等。