这是一个创建于 375 天前的主题，其中的信息可能已经有所发展或是发生改变。
n 种不同面值的马内，并且每种的数量有限
给出一个指定金额，凑够这个金额。有多少种组合方法
如果凑不到这个金额，比如只有 1 元和 0.5 元，金额是 1.1 元，则取 1.5 来凑
 |
1
yumenawei 2023-12-13 10:53:57 +08:00
有个大概想法，不确定是否正确。
假如有面值为：1 3 5 的钱。 设 dp[i] 为凑够 i 元的方案数。 那么 dp[i] = dp[i-1] + dp[i-3] + dp[i-5]，即凑够 i 的方案可以由：i-1 的方案加 1 元 和 i-3 的方案加 3 元 和 i-5 的方案加 5 元凑成。 如果最后不是正好凑齐的金额，就在金额附近做一个遍历查找最靠近金额的有方案的值。 |
 |
2
murmur 2023-12-13 11:18:50 +08:00
直接发原题吧，现实场景还不是动态规划 算也是 mod 100 后的结果算，整票子就用 100 元
|
 |
3
abc0123xyz OP @murmur #2
原题是 寄信的时候凑邮资....................... |
Select Language