证明这个算法最优
有硬币面值25分，10分，5分，1分。
要找的硬币数目最少。
找零钱时，从大往小找。
如，67分，
25*2+10+5+1*2，
此种找法最优。请证明（用数学方法）。
若硬币面值不同，为任意值（大面值不能由小面值斗出，如50，40，29，1），
何种算法最优？
问题点数：50、回复次数：8Top
1 楼quicmous（快鼠）回复于 2002-07-13 23:53:16 得分 0
大票换成小票，当然票子的数量会增加。小票尽量换成大票，票子的数量就会减少。这种问题不需要进行复杂的论证吧！Top
2 楼hy_bug（蓝虫）回复于 2002-07-14 00:08:04 得分 0
若面值不规则呢？
大票不能换成整数张小票Top
3 楼chenggn（chenggn）回复于 2002-07-14 00:19:40 得分 0
这个问题 可以归结 减去一个可减的最大值 后为同类的更小问题
若硬币面值不同，为任意值 种算法最优？
肯定是这样的！ 贪心嘛！！！
Top
4 楼chenggn（chenggn）回复于 2002-07-14 00:23:04 得分 0
比如 100 的rmb 3张
和10 元rmb 4张
让你取4张 取面值得最大
肯定是现取完了 100 的再说 有100 的就不要10的
通用的对于任何问题
证明是否可用贪心法 通常使用矩阵赔理论 不过我不太懂
至于证明这个题 线性规划吧
Top
5 楼chenggn（chenggn）回复于 2002-07-14 00:31:04 得分 0
若面值不规则呢？
大票不能换成整数张小票
根这没关系！
难道 。。。
你自己想吧。
利清头绪 别把问题搞混了
附： 证明如下
f(N)表示N用M张面值为 m1, m2, m3... mm 【降序排列】的面值的最少张数。
显然有 f(N)= min{f(N-m1)+1 , f(N-m2)+1,.... }
显然 f(N-m[i+1])>=f(N-m[i])
所以得证
f(N)表示N用M张面值为 m1, m2, m3... mm （降序排列）的面值的最少张
f(N)= f(N-m1)+1Top
6 楼quicmous（快鼠）回复于 2002-07-15 00:03:53 得分 0
呵呵，我给个证明吧！
命题1 如果硬币只有8,7,1两种，对于任意整数N，试图先用大面值硬币后用小面值硬币组合出该数量，硬币数量并不能总是达到最小。
证明：
取N=14,则
N = 8 + 1 + 1 + 1 + ... + 1 ,共7枚硬币
同时
N = 7 + 7，共两枚硬币。
命题得证。
注：主要原因是8 < 7 + 7
========================================================
命题2
有硬币面值25分，10分，5分，1分。
要找的硬币数目最少。
找零钱时，从大往小找。
证明：
因为：
25 >= 10 + 10
10 >= 5 + 5
5 >= 1 + 1
因此，命题得证。
Top
7 楼quicmous（快鼠）回复于 2002-07-15 00:41:55 得分 50
可以用数学归纳法证明，如果数列a[1],a[2],...,a[n]满足：
a[1]=1,a[1]+a[1]<=a[2],a[2]+a[2]<=a[3],...,那么首先选择最大的数列项必然导致硬币总数最少。
证明：
(1)n=1时，只有一枚面值为1的硬币，命题显然正确。
(2)设n=k时，命题正确。则n=k+1时，
设给定金额N，用a[1],a[2],...,a[k]得到的最优解是 m 枚硬币，
如果N < a[k+1]，则用a[1],a[2],...,a[k+1]得到的最优解是 m 枚硬币;
如果N >= a[k+1]，则必然可以用a[k+1]代替多于1个的a[1],...,a[k]，用a[1],a[2],...,a[k+1]得到的最优解必然少于 m 枚硬币;
因此,n=k+1时命题(首先选择最大的数列项必然导致硬币总数最少)仍然成立.
所以，对于任意自然数n,原命题成立！
Top
