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] 或 dp[j − x_i]  （如果 j − x_i ≥ 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 背包需要倒序遍历，确保每枚硬币只选一次。