[已解决]Python：每日一题 314

wanting-for

zltzlt 发表于 2020-1-25 22:11
输入 amount = 500，coins = [1, 2, 5] 就会超时

算法不好，有待更改，迷上了递归，看见啥都想递归一下
这个用例大约用时15秒

zltzlt

wanting-for 发表于 2020-1-25 22:21
算法不好，有待更改，迷上了递归，看见啥都想递归一下
这个用例大约用时15秒

小心超出递归深度

wanting-for

zltzlt 发表于 2020-1-25 22:22
小心超出递归深度

嘿嘿，我想到优化方法了

776667

from itertools import product

def fun314(amount,coins):
    if amount%min(coins):
        repeat = (amount//min(coins))+1
    else:
        repeat = amount//min(coins)
    result = []
    for i in range(1,repeat+1):
        for j in product(coins,repeat=i):
            if sum(j)==amount and sorted(j) not in result:
                result.append(sorted(j))
    return len(result)

fan1993423

Croper 发表于 2020-1-25 15:18
总感觉还能优化

你这道题的想法是什么？

Croper

fan1993423 发表于 2020-1-31 23:12
你这道题的想法是什么？

还是动态规划。
在把硬币面值数组coins从小到大排序后，
使用l[a][ b]储存在要求金额为a时，使用前b+1种硬币能凑出的方案数量。
显然在a=0时，不管b为多少，结果都为0(不取任何硬币)。
在a!=0时，考虑凑出的方案中面值最大硬币其面值为coins[c]，那么剩余的硬币金额都不大于coins[c],可用方案数量为l[a-coins[c]][c]。且有c不大于 b。
即状态转移公式为l[a][ b]=l[a-coins[0]][0]+l[a-coins[1]][1]+...+l[a-coins[ b]][ b]
最终答案就为l[amount][len(coins)-1]

fan1993423

def fun314(amount,coins):
    coins.sort()
    dp=[[1]+[0]*amount for _ in range(len(coins)+1)]
    for i in range(1,len(coins)+1):
        for j in range(1,amount+1):
            if j>=coins[i-1]:
                dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
            else:
                dp[i][j]=dp[i-1][j]
    return dp[-1][-1]

kinkon

fan1993423 发表于 2020-4-17 02:04

虽然费空间，但是清晰易懂，赞

fan1993423

kinkon 发表于 2020-4-17 21:53
虽然费空间，但是清晰易懂，赞

zltzlt

fan1993423 发表于 2020-4-17 02:04

输入 amount = 11, coins = [1, 2, 5] 结果有误

fan1993423

zltzlt 发表于 2020-4-18 13:28
输入 amount = 11, coins = [1, 2, 5] 结果有误

难道输出的结果不是11吗？

zltzlt

fan1993423 发表于 2020-4-18 15:05
难道输出的结果不是11吗？

是 3

fan1993423

zltzlt 发表于 2020-4-18 17:01
是 3

难道我的理解有误
11=11*1+0*2+0*5
=9*1+1*2+0*5
=7*1+2*2+0*5
=5*1+3*2+0*5
=3*1+4*2+0*5
=1*1+5*2+0*5
=6*1+0*2+1*5
=4*1+1*2+1*5
=2*1+2*2+1*5
=0*1+3*2+1*5
=1*1+0*2+2*5
共计11种方案，而且你选的最佳答案在输入(11，[1,2,5]）也是输出的11

zltzlt

fan1993423 发表于 2020-4-18 20:56
难道我的理解有误
11=11*1+0*2+0*5
=9*1+1*2+0*5

额……测试用例出错了

fan1993423

zltzlt 发表于 2020-4-19 13:21
额……测试用例出错了

耗时怎么样