算法之Python实现 - 001 : 换钱的最少货币数
2024-09-11 20:47:02
【题目】给定数组arr,arr中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求组成aim的最少货币数。
【代码1】:时间与额外空间复杂度O(N*aim)
import numpy as np
from xmlrpc.client import MAXINT def mincoin(arr,aim):
if len(arr)<0:
print("No coin provided for change!")
arr.sort()
arr.reverse()
if aim == 0:
print("Aim is 0, no need to change!")
dp = np.zeros((len(arr),aim+1))
i = 0
j = 0
left = aim
maxval = MAXINT for j in range(1,aim+1):
dp[0][j] = maxval
if j-arr[0] >=0 and dp[0][j-arr[0]] != maxval:
dp[0][j] = dp[0][j-arr[0]]+1 for i in range(1,len(arr)):
for j in range(1,aim+1):
left = maxval
if j-arr[i] >=0 and dp[i][j-arr[i]] != maxval:
left = dp[i][j-arr[i]]+1
dp[i][j] = min(left,dp[i-1][j]) print('Need ',int(dp[len(arr)-1][aim]),' Coins.') # ===CALL === #
a = [3,5,2]
tar = 20
mincoin(a,tar)
【代码2】:时间复杂度O(N*aim),额外空间复杂度O(aim)
import numpy as np
from xmlrpc.client import MAXINT def mincoin(arr,aim):
if len(arr)<0:
print("No coin provided for change!")
arr.sort()
arr.reverse()
if aim == 0:
print("Aim is 0, no need to change!")
dp = np.zeros((1,aim+1))[0]
i = 0
j = 0
maxval = MAXINT for j in range(1,aim+1):
dp[j] = maxval
if j-arr[0] >=0 and dp[j-arr[0]] != maxval:
dp[j] = dp[j-arr[0]]+1 left = 0
for i in range(1,len(arr)-1):
for j in range(1,aim+1):
left = maxval
if j-arr[i] >=0 and dp[j-arr[i]] != maxval:
left = dp[j-arr[i]]+1
dp[j] = min(left,dp[j]) #print(dp)
print('Need ',int(dp[aim]),' Coins.') # ===CALL === #
a = [5,2,3]
tar = 20
mincoin(a,tar)
【代码3】:时间复杂度O(N*aim),额外空间复杂度O(aim)
在原书也就是【代码2】的基础上,下面的执行效率会更高一点点,但是这种算法对于【代码1】的复杂度是有问题的。
import numpy as np
from xmlrpc.client import MAXINT def mincoin(arr,aim):
if len(arr)<0:
print("No coin provided for change!")
arr.sort()
arr.reverse()
if aim == 0:
print("Aim is 0, no need to change!")
dp = np.zeros((1,aim+1))[0]
i = 0
j = 0
maxval = MAXINT for j in range(1,aim+1):
dp[j] = maxval
if j-arr[0] >=0 and dp[j-arr[0]] != maxval:
dp[j] = dp[j-arr[0]]+1 left = 0
for i in range(1,len(arr)):
for j in range(j-arr[i],aim+1):
left = maxval
if dp[j-arr[i]] != maxval:
left = dp[j-arr[i]]+1
dp[j] = min(left,dp[j]) #print(dp)
print('Need ',int(dp[aim]),' Coins.') # ===CALL === #
a = [5,2,3]
tar = 20
mincoin(a,tar)
最新文章
- BZOJ4533 [BeiJing2014 WinterCamp] 数据
- C# webbrowser实现真正意义上的F5刷新
- Webbench网站压力测试
- openstack 网卡
- 圆形DIV
- Spring AOP Interceptor transaction is not working
- cloudstack4.2+xenserver6.0.2 详细配置攻略
- POJ 3321 Apple Tree(dfs序树状数组)
- 构造Scala开发环境并创建ApiDemos演示样例项目
- win10 uwp 绑定密码
- 解析JSON的三种方式
- CF 552 Neko does Maths
- ThreadPoolExecutor系列一——ThreadPoolExecutor 机制
- Spring 通知和顾问进行增强
- Android环境搭建(大学授课课件)
- 论文阅读笔记十:DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs (DeepLabv2)(CVPR2016)
- Dethe is my Finaunce金融
- java实现网页验证码
- iptabes一条指令开放多个端口
- Jumpserver3.0部署(Centos6.x)