题目描述：

给定一组不同面额的硬币（保证包含面额 1 且相邻面额是倍数关系），和一个目标金额 amount，要求你找出最少的硬币数目，使得硬币的总金额等于目标金额。

要求：

• 你可以使用任意数量的硬币。
• 你需要选择硬币的组合，使得总金额等于目标金额，并且硬币的数量最少。
• 如果无法组合成目标金额，返回 -1。

输入格式：

• 第一行包含一个整数 n，表示硬币的数量。$1$ ≤ n ≤ $20$
• 第二行包含 n 个整数，表示硬币的面额coins，保证每个面额都大于0且相邻的面额满足倍数关系，且包含面额 1。$1$ ≤ coins[i] ≤ $10^9$
• 第三行包含一个整数 amount，表示目标金额。$1$ ≤ amount ≤ $10^9$

输出格式：

• 输出一个整数，表示能够凑成目标金额所需的最少硬币数目。如果无法凑成目标金额，输出 -1。

示例：

输入：

5
1 5 10 20 100
66

输出：

5

说明：

• 你可以选择硬币 20 + 20 + 20 + 5 + 1，总金额为 11，硬币数目为 3。
• 所以最少硬币数为 5。

【贪心4】零钱兑换问题

题目简述：

给定一组硬币的面额，其中包含面额 1 且相邻面额满足倍数关系，和一个目标金额 amount。要求找出最少的硬币数目，使得硬币的总金额等于目标金额。如果无法组合成目标金额，返回 -1。

解题思路：

该问题可以通过 贪心算法 来解决。因为题目给定的硬币面额满足倍数关系，贪心算法在这种情况下是最优的。具体来说，贪心策略是优先选择面额较大的硬币，这样能尽可能少地使用硬币来达到目标金额。

贪心算法的思路：

1. 排序硬币：先将硬币按面额从大到小排序，这样我们就可以从最大面额的硬币开始尝试。
2. 从大到小选硬币：对于每种硬币，尽可能多地使用该硬币，直到剩余金额无法再使用该硬币为止，然后继续选择下一个较小的硬币。
3. 结束条件：当目标金额 amount 减为零时，表示已经找到了解决方案；如果遍历所有硬币后仍然无法达到目标金额，则返回 -1。

贪心策略正确性的证明：

反证法

1. 假设存在一个更优解，它不使用 $a_i$，而是使用若干个小于 $a_i$ 的硬币。
2. 设 $a_{i - 1}$ 是小于 $a_i$ 的最大面额。 根据倍数关系，有 $a_{i} = k\ ×\ a_{i-1} (k ≥ 2)$
3. 要凑出 $a_i$ 的金额，至少需要 $k$ 个 $a_{i - 1}$。 因为 $k ≥ 2$，所以需要至少 2 个 $a_{i - 1}$。
4. 而使用 $a_i$ 只需要 1 个硬币。
5. 因此，使用小于 $a_i$ 的硬币组合一定不会比直接使用 $a_i$ 更优。

代码实现：

def minCoins(coins, amount):
    # 将硬币按面额从大到小排序
    coins.sort(reverse=True)
    
    # 初始化硬币数目
    coin_count = 0
    
    # 遍历硬币，尝试从大到小使用硬币
    for coin in coins:
        if amount == 0:
            break
        # 使用尽可能多的当前硬币
        coin_count += amount // coin
        amount %= coin  # 更新剩余金额
    
    # 如果amount变为0，说明找到了最小硬币数
    if amount == 0:
        return coin_count
    else:
        return -1  # 如果无法组合成目标金额，返回-1

# 输入处理部分
n = int(input())  # 硬币数量
coins = list(map(int, input().split()))  # 硬币面额
amount = int(input())  # 目标金额

# 输出最少硬币数
print(minCoins(coins, amount))