动态规划问题之贪婪算法实现硬币最优解

动态规划问题之贪婪算法实现硬币最优解

贪婪问题实现最少的硬币找零问题：
start_time = time.time()
end_time = time.time()
print(‘Took %f second’ % (end_time - start_time))
是我们加入用来计算运算时间的

首先定义一个函数：rec(coinValueList,change) 其中coinValueList是我们的硬币的面值，change是我们的需要找零的金额
[c for c in coinValueList if c<=change]：这里创建一个列表用来存储这次找零可以用到的面值金额，然后进行循环调用和递归运算。

import time
start_time = time.time()

def rec(coinValueList,change):
    minCoins=change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c<=change]:
            numCoins=1+rec(coinValueList,change-i)
            if numCoins<minCoins:
                minCoins=numCoins
    return minCoins
print(rec([1,5,10,25],63))
end_time = time.time()
print('Took %f second' % (end_time - start_time))

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

我们可以看出这种算法耗时非常多，需要进行优化：
加入一个可查询的列表，就不用重复计算已经算过的此面值最优的找零方法，可以节约非常巨大的一部分时间。

import time
start_time = time.time()

def rec(coinValueList,change,list):
    minCoins=change
    if change in coinValueList:
        list[change]=1
        return 1
    elif list[change]>0:
        return list[change]
    else:
        for i in [c for c in coinValueList if c<=change]:
            numCoins=1+rec(coinValueList,change-i,list)
            if numCoins<minCoins:
                minCoins=numCoins
                list[change]=minCoins
    return minCoins
print(rec([1,5,10,25],63,[0]*64))
end_time = time.time()
print('Took %f second' % (end_time - start_time))

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

文章来源: xuyipeng.blog.csdn.net，作者：是Dream呀，版权归原作者所有，如需转载，请联系作者。

原文链接：xuyipeng.blog.csdn.net/article/details/119205911