证明这个算法最优
有硬币面值25分，10分，5分，1分。 要找的硬币数目最少。 找零钱时，从大往小找。 如，67分， 25*2+10+5+1*2， 此种找法最优。请证明（用数学方法）。 若硬币面值不同，为任意值（大面值不能由小面值斗出，如50，40，29，1）， 何种算法最优？
大票换成小票，当然票子的数量会增加。小票尽量换成大票，票子的数量就会减少。这种问题不需要进行复杂的论证吧！
若面值不规则呢？ 大票不能换成整数张小票
这个问题 可以归结 减去一个可减的最大值 后为同类的更小问题 若硬币面值不同，为任意值 种算法最优？ 肯定是这样的！ 贪心嘛！！！
比如 100 的rmb 3张 和10 元rmb 4张 让您取4张 取面值得最大 肯定是现取完了 100 的再说 有100 的就不要10的 通用的对于任何问题 证明是否可用贪心法 通常使用矩阵赔理论 不过我不太懂 至于证明这个题 线性规划吧
若面值不规则呢？ 大票不能换成整数张小票 根这没关系！ 难道 。。。 您自己想吧。 利清头绪 别把问题搞混了 附： 证明如下 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)+1
呵呵，我给个证明吧！ 命题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 因此，命题得证。
可以用数学归纳法证明，假如数列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,原命题成立！
