HDU 2546 飯卡問題：0-1背包變體求最小餘額

HDU 2546 是經典的 0-1 背包變體：食堂刷卡有「餘額 ≥ 5 即可任意消費」的特殊規則。求購買所有菜品後的最小餘額。

問題建模

• n 道菜，價格 price[i]，每道買一次
• 初始餘額 sum
• 規則：當前餘額 ≥ 5 時，可購買任意價格的菜（甚至價格 > 餘額）
• 目標：最小化最終餘額

關鍵洞察

1. 「餘額 ≥ 5 可透支」等價於：只能在餘額 > 5 時購買，購買後餘額可 < 5
2. 最後一次購買前餘額必須 ≥ 5，最後購買後可 < 5
3. 轉化為：從 sum 開始，每次減去 price[i]，中間狀態必 ≥ 5，終態可 < 5
4. 這是「可達性」背包：dp[j] 表示餘額 j 是否可達

狀態轉移

// 物品價格按升序排序（關鍵！）
sort(price+1, price+n+1);

dp[sum] = 1;  // 初始狀態可達
minRem = sum;

for i = 1..n:
    for j = 5..sum:           // 正序遍歷！保證用上一輪狀態
        if dp[j]:
            if j - price[i] >= 5:
                dp[j - price[i]] = 1;
            if j - price[i] < minRem:
                minRem = j - price[i];  // 記錄最小可達餘額

為什麼要升序排序 + 正序遍歷？

• 大價格先處理會過早把餘額推到 < 5，導致小價格無法使用
• 正序遍歷（5→sum）保證狀態轉移基於「未選當前物品」的舊狀態，符合 0-1 背包「每件只能用一次」
• 逆序遍歷會導致同一物品被多次使用（變成完全背包）

完整 AC 代碼

#include 
#include 
#include 
using namespace std;

#define MAX 100000
int n, price[MAX], sum, minRem, dp[MAX];

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; i++) scanf("%d", &price[i]);
        scanf("%d", &sum);
        sort(price + 1, price + n + 1);

        memset(dp, 0, sizeof(dp));
        dp[sum] = 1;
        minRem = sum;

        for (int i = 1; i <= n; i++)
            for (int j = 5; j <= sum; j++)
                if (dp[j]) {
                    if (j - price[i] >= 5)
                        dp[j - price[i]] = 1;
                    if (j - price[i] < minRem)
                        minRem = j - price[i];
                }

        printf("%d\n", minRem);
    }
    return 0;
}

測試樣例

Input:
3
10000 1 3
9
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
3
1 2 3
3
0

Output:
4
5
15
3

複雜度分析

• 時間：O(n × sum) —— sum ≤ 1000，n ≤ 1000，約 10⁶ 操作，極快
• 空間：O(sum) —— 一維 DP 數組

常見錯誤總結

結語

HDU 2546 巧妙地將「餘額 ≥ 5 可透支」轉化為背包可達性問題。核心技巧：排序 + 正序遍歷 + 狀態可達性。這類「特殊約束轉標準模型」的題目，關鍵在於抓住約束的本質邊界（此處為「最後一次購買前必 ≥ 5」），再選擇正確的 DP 遍歷順序保證物品不重複使用。