贪心算法 - 算法基础

零钱兑换 (Coin Change)

假设有面额为 20, 10, 5, 1 的硬币，如何用最少的通过硬币数量凑出目标金额？

贪心策略：每次优先尽可能选最大的面额。

目标金额:

设置金额并点击开始

注意：贪心法在某些特定的货币系统下（如 1, 3, 4 凑 6，贪心选 4+1+1 共3枚，实际 3+3 共2枚）会失效！但在标准货币系统下通常有效。

int coins[] = {20, 10, 5, 1};
int target = 46;

for(int c : coins) {
    while(target >= c) {
        target -= c;
        // 选了一枚 c
    }
}