寒冰王座：C 語言暴力搜尋解背包問題變體

問題背景

死亡騎士要購買三種價格分別為 350、200、150 的物品，給定總金額 money，求花費最接近但不超過 money 的組合，輸出最少小費（即 money - max_cost）。

解法策略

因面額較大且數量有限（money/150 最大約 66），三層巢狀迴圈暴力枚舉所有組合可行。時間複雜度約 O((money/150)³)，實測極快。

核心程式碼

#include <stdio.h>

int main() {
    int i, j, k, n, m, l, num, max, cost, money;

    scanf("%d", &num);
    while (num--) {
        scanf("%d", &money);
        n = money / 350;
        m = money / 200;
        l = money / 150;
        max = 0;

        for (i = 0; i <= n; i++)
            for (j = 0; j <= m; j++)
                for (k = 0; k <= l; k++) {
                    cost = i * 350 + j * 200 + k * 150;
                    if (cost > max && cost <= money) max = cost;
                }

        printf("%d", money - max);
        if (num > 0) printf("\n");
    }
    return 0;
}

優化方向

• 可改用動態規劃（0-1 背包/完全背包）將複雜度降至 O(money × 物品種類)
• 或利用數學觀察：gcd(350,200,150)=50，金額對 50 取模後僅需檢查少數情況

執行結果