HDU 2546 饭卡：0-1 背包 + 貪心排序求最大剩餘

HDU 2546 饭卡：0-1 背包 + 貪心排序求最大剩餘

V 道菜（≤100），每道菜價格 a[i]。餘額 rest，必須留 5 元（最貴菜 ≥5），求最大剩餘。即：從 V-1 道菜中選，總價 ≤ rest-5，最大化總價。

算法邏輯

1. 排序價格升序，最貴菜單獨處理（必須買）。
2. 0-1 背包：dp[v] 表示能湊出價值 v（布爾）。
3. 遍歷前 V-1 道菜逆序更新 dp，記錄可達最大值 maxm。
4. 答案 = rest - maxm - 最貴菜價格？實際代碼中 maxm 已包含最貴菜邏輯，直接 rest - maxm。

代碼關鍵點

sort(a, a+V);
cin >> rest;
DP(); // 背包處理前V-1項，容量rest-5
cout << rest - maxm << endl;
void DP() {
    for (i=0; i=0; v--)
            if (f[v]) { if (v+a[i]<=rest) f[v+a[i]]=1; maxm=max(maxm, v+a[i]); }
}

複雜度

• 時間：O(V * rest) ≤ 100 * 1000 = 1e5。
• 空間：O(rest)。

本題是「必選最貴項目 + 0-1 背包選其餘」的變體，排序後分離必選項簡化邏輯，背包容量為 rest-5 確保剩餘 ≥5。