HDU 5188 限制條件 01 背包：時間約束下的動態規劃

問題描述

有 n (≤30) 個物品，第 i 個耗時 t_i、價值 v_i、最早可完成時間 l_i（在此之前完成會被判定作弊）。需選擇物品使總價值 ≥ w，求最小總耗時。物品不可分割，一次只能做一個。

關鍵轉化

物品 i 若在時刻 T 完成，需滿足 T ≥ l_i。即其開始時間 ≥ l_i - t_i。為了讓 DP 狀態合法，按 l_i - t_i 從小到大排序。這樣在考慮前 i 個物品時，當前時間 T 若 ≥ l_i - t_i，則後續物品的限制自動滿足（因為它們的 l-t 更大）。

DP 定義與轉移

• dp[j]：花費總時間恰為 j 所能獲得的最大價值。
• 初始 dp[0]=0，其餘 -INF。
• 按排序後順序遍歷物品，對時間 j 從大到小更新（01 背包）：
   若 j ≥ t_i 且 j ≥ l_i，dp[j] = max(dp[j], dp[j-t_i] + v_i)。
• 最終掃描 dp[j] ≥ w 的最小 j。

時間上界優化

最大時間上界 up = max(∑t_i, max l_i)。實際只需 DP 到 up。

代碼框架

struct Item { int t, v, l; };
bool cmp(Item a, Item b) { return a.l - a.t < b.l - b.t; }

int dp[MAX_TIME];
while (scanf("%d%d", &n, &w) != EOF) {
    for (int i=0;i=item[i].t; --j) {
            if (j >= item[i].l)
                dp[j] = max(dp[j], dp[j-item[i].t] + item[i].v);
        }
    }
    int ans = -1;
    for (int j=0;j<=up;++j) if (dp[j] >= w) { ans=j; break; }
    if (ans==-1) puts("zhx is naive!");
    else printf("%d\n", ans);
}

總結

HDU 5188 是帶時間窗約束的 01 背包。核心技巧：按 l-t 排序將時間約束轉化為 DP 狀態的合法性條件，配合滾動數組優化空間。體現了「排序 + DP」在約束優化問題中的通用思想。