Money Sums 题解

题目描述

https://cses.fi/problemset/task/1740

给定 n 枚硬币，每枚硬币价值 $x_i$，求能凑成的所有不同金额。

限制：

• 1 ≤ n ≤ 100
• 1 ≤ $x_i$ ≤ 1000

示例：

• 输入：4, coins = [4, 2, 5, 2]
• 输出：9 种金额：2 4 5 6 7 8 9 11 13

---

解法

问题类型：0-1 背包（每枚硬币只能用一次，求能凑成的金额）

定义：dp[j] 表示能否凑成金额 j（True/False）

初始条件：dp[0] = True（金额 0 可以凑成：什么都不选）

状态转移：

$$dp[j] = dp[j] \text{ 或 } dp[j - x_i] \quad \text{（如果 } j - x_i \geq 0）$$

解释：遍历每枚硬币，尝试将其加入已凑成的金额中。倒序遍历确保每枚硬币只用一次。

代码

n = int(input())
coins = list(map(int, input().split()))

max_sum = sum(coins)
dp = [False] * (max_sum + 1)
dp[0] = True

for coin in coins:
    for j in range(max_sum, coin - 1, -1):
        if dp[j - coin]:
            dp[j] = True

res = [i for i in range(1, max_sum + 1) if dp[i]]

print(len(res))
print(*res)

时间复杂度：O(n × max_sum)
空间复杂度：O(max_sum)

注意：0-1 背包需要倒序遍历，确保每枚硬币只选一次。