最少硬币找零算法.pptx

最少钱币问题
问题描述:
设有n种不同面值的硬币,各硬币的面值存在于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0m20001,设计一个最少硬币找钱m的方法。
算法设计:
对于给定的1n10 ,硬币面值数组T和可以使用的各种面值的硬币数组Coins,以及钱数m, 0m20001,计算找钱m的最少硬币数。
定义数据结构:
count_item
当Num=0且coins[]为初始情况表示没有该选取方式的可能性
0
m
算法描述:
计数数组 count[n][m]
count[j][i]:表示当钱数为 i 时,一定选取
T[j]的钱币剩余情况,
n(j)
money(i)
i -T[j]
选取T[j],则剩余钱数为i-T[j]
扫描
算法描述:
情况一:i – T[j] 列中均为无法选取的情况(判断标志Num=0),
此时判断(T[j]== i),如果相等且(coins[j]!=0)则
设置count[j][i].Num=1,否则设置为 0
情况二: i - T[j]列中存在至少一个的可选情况
(Num>0且count[][i-T[j]].coins[j]>0)则将
count[j][i].Num= count[][i-T[j]].Num+1,再将coins[]对应硬币 减一赋给count[j][i].coins[].
例子:
n\m
0
1
2
3
4
5
6
7
8
9
10
1(1)
0
(4,2,2)
1
(3,2,2)
2
(2,2,2)
3
(1,2,2)
4
(0,2,2)
0
(4,2,2)
2
(3,1,2)
2
(3,2,1)
3
(