POJ 3040 Allowance：貪心策略求最大發薪週數

問題描述

農夫約翰有 N 種面額的硬幣（1 ≤ N ≤ 20），每種面額是下一種面額的整數倍（如 1, 5, 10, 50 分）。每種硬幣有限數量。每週需支付貝西至少 C 元（1 ≤ C ≤ 100,000,000）。求最多能支付多少週。

貪心策略核心

利用面額之間的「整數倍」關係（即每種面額 ≥ 2 倍前一種），可採用以下分階段貪心：

1. 大面額優先直接支付：面額 ≥ C 的硬幣，每枚可獨立支付一週，直接累加數量。
2. 組合湊齊 C：對於面額 < C 的硬幣，從大到小嘗試湊出恰好 C；若無法湊齊，則取盡可能大的組合（和 < C），再用較小面額補齊。
3. 批量計算可重複週數：每次確定一組硬幣組合後，計算該組合最多能重複多少週（受限於最稀缺硬幣），批量扣除並累加答案。

正確性論證

因為面額遞增至少 2 倍，任何面額都大於所有較小面額之和。這保證了「優先使用大面額」不會錯失最優解：若大面額能湊出 C，一定優於用小面額湊；若湊不出，用最大的不超過 C 的組合再補小面額是最優的。

程式碼實現（C++）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct Coin { int val, num; } coins[25];
int need[25];

bool cmp(const Coin& a, const Coin& b) { return a.val > b.val; }

int main() {
    int n, C;
    while (cin >> n >> C) {
        for (int i = 0; i < n; ++i) cin >> coins[i].val >> coins[i].num;
        sort(coins, coins + n, cmp);

        long long weeks = 0;
        int idx = 0;
        // 階段 1：面額 >= C 直接用
        for (; idx < n; ++idx) {
            if (coins[idx].val < C) break;
            weeks += coins[idx].num;
        }

        // 階段 2：反覆湊組合
        while (true) {
            memset(need, 0, sizeof(need));
            int rest = C;
            // 從大到小盡量湊
            for (int i = idx; i < n; ++i) {
                if (!coins[i].num || !rest) continue;
                int take = min(coins[i].num, rest / coins[i].val);
                need[i] = take;
                rest -= take * coins[i].val;
            }
            // 需要小面額補齊
            if (rest) {
                for (int i = n - 1; i >= idx; --i) {
                    if (coins[i].val >= rest && coins[i].num > need[i]) {
                        ++need[i];
                        rest = 0;
                        break;
                    }
                }
                if (rest) break; // 無法湊齊
            }
            // 計算可重複週數
            int repeat = 1e9;
            for (int i = idx; i < n; ++i)
                if (need[i]) repeat = min(repeat, coins[i].num / need[i]);
            if (!repeat) break;
            weeks += repeat;
            for (int i = idx; i < n; ++i) coins[i].num -= repeat * need[i];
        }
        cout << weeks << endl;
    }
    return 0;
}

複雜度分析

• 時間：O(N² log C) —— 每次迴圈至少消耗一種硬幣，N ≤ 20 極小。
• 空間：O(N)。

總結

本題利用面額的倍數關係，將問題轉化為反覆「湊組合 + 批量重複」的貪心過程。關鍵在於識別「大面額優先」的最優子結構，並處理湊不齊時的補齊邏輯。