C語言背包問題變體：寒冰王座最小小費計算（完全背包/暴力枚舉）

問題背景

死亡騎士有 money 金幣，地精商人出售三種物品：350、200、150 金幣。騎士想花費盡可能多的金幣（不超過擁有金額），剩餘金幣作為小費給商人。求最小小費（即 money - max_spend）。

算法分析

這是一個 完全背包問題 變體：物品無限供給，背包容量 money，物品價值即重量（350,200,150），目標最大化總價值不超過容量。

原始代碼：三層暴力枚舉

for i=0..money/350
  for j=0..money/200
    for k=0..money/150
      cost = 350i+200j+150k
      if cost<=money && cost>max) max=cost;

時間複雜度 O((M/150)³) ≈ O(M³)，M≤10⁵ 時極慢，僅適合極小數據範圍。

優化方案一：動態規劃（完全背包標準解法）

dp[c] 表示花費恰好 c 金幣是否可行。初始 dp[0]=true，對每種物品價格 w，for c=w..money: dp[c] |= dp[c-w]。最後從 money 向下找第一個 true。複雜度 O(3×M) = O(M)。

優化方案二：數學觀察（gcd 剪枝）

三數 350,200,150 的 gcd = 50。故可行花費必為 50 的倍數。將問題縮小 50 倍：容量 M'=money/50，物品 {7,4,3}。再用 DP 或枚舉，再乘回 50。

高效 DP 實現代碼

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_M 100000

int main() {
    int T, money;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &money);
        static bool dp[MAX_M + 1];
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        int items[3] = {350, 200, 150};
        for (int k = 0; k < 3; k++) {
            int w = items[k];
            for (int c = w; c <= money; c++) {
                if (dp[c - w]) dp[c] = true;
            }
        }
        int max_spend = money;
        while (max_spend >= 0 && !dp[max_spend]) max_spend--;
        printf("%d\n", money - max_spend);
    }
    return 0;
}

進階優化：滾動數組 + 位運算加速

使用 unsigned long long 位圖表示 dp 狀態，每 64 位一組，利用位移與或運算批量更新，可再提升 64 倍常數因子。

測試樣例

Input:
1
1000
// 可組合：350*2+150*2=1000 恰好花完
Output:
0

擴展思考

• 若物品種類增加至 n，DP 複雜度 O(n×M) 仍可接受。
• 若 money 極大（10⁹），需用數學方法（擴展歐幾里得/弗羅貝尼烏斯硬幣問題）求解最大不可表示數。
• 引入物品數量限制（0-1 背包/多重背包），改用二進制拆分或單調隊列優化。