硬币找零问题：贪心算法与动态规划

///'硬币找零问题///'设有n种零钱, 重量分别为w=w//_1,w//_2,//dots,w//_n, 价值分别为p=1,p//_1,p//_2,//dots,p//_n。需要用这些硬币付款的总钱数是Y。问: 如何选择这些硬币而使得付钱的硬币总重最轻? 1) 若使用贪心法求解硬币找零问题，允许使用前k种零钱，总钱数为y时得到的总重设为G(y)，请给出子问题最优解值Gk(y)的递推方程。 2) 若使用动态规划求解硬币找零问题，允许用前k种零钱，总钱数为的最小重量设为F(V)，请给出子问题最优解值F(v)的递推方程。 3) 对于硬币找零问题，有如下定理: 对每个k e Z//+，假设对所有非负整数y，有Gk(y)= Fk(y)且存在z//+,z//+和//d满足 Pk+1=zpk-//d, 0<//d<pk, Pk+i>pk 则以下命题等价: Gr+1(y)=F//_r+1(y)，对一切正整数y; 2Gk+i(zpi)=F//_ti(zp)3)wr.+G(//d)<ZW. 试应用以上定理求解找硬币问题的实例: p=1,p//_1=5,p//_2=16,p//_3=18,w//_i=1,i=1,2,3,4问对于这个硬币系统，贪心法能否对所有y正确工作? 如果不能，找出反例。 给出正确的解答步骤内容：1) 贪心法的递推方程为： Gk(y) = min(Gk-1(y), Gk(y-pk) + wk) 其中，Gk-1(y)表示只使用前k-1种零钱时，总钱数为y时得到的总重量；Gk(y-pk)表示使用前k种零钱，总钱数为y-pk时得到的总重量，再加上第k种零钱的重量wk。 2) 动态规划的递推方程为： Fk(v) = min(Fk-1(v), Fk(v-pk) + wk) 其中，Fk-1(v)表示只使用前k-1种零钱时，总钱数为v时的最小重量；Fk(v-pk)表示使用前k种零钱，总钱数为v-pk时的最小重量，再加上第k种零钱的重量wk。 3) 根据定理，命题1、2、3等价，即Gr+1(y)=F//_r+1(y)，对一切正整数y；2Gk+i(zpi)=F//_ti(zp)；wr.+G(//d)<ZW。 4) 对于硬币系统p=1, p//_1=5, p//_2=16, p//_3=18, w=1, i=1,2,3,4。我们可以先计算出G1(y)和F1(v)，再根据定理来验证贪心法的正确性。 首先，计算G1(y)和F1(v)： G1(y) = min(G0(y), G1(y-1) + 1) = min(0, G1(y-1) + 1) F1(v) = min(F0(v), F1(v-1) + 1) = min(0, F1(v-1) + 1) 然后，验证定理中的等式： G2(y) = F2(y) （命题1） G2(1) = F2(1) （命题2） 接下来，根据定理中的不等式wr.+G(//d)<ZW，来验证贪心法的正确性。 w1 + G1(8) < w1 + F1(8) （命题3） 通过计算可以得到： w1 + G1(8) = 1 + G1(8) = 1 + G1(7) + 1 = 2 + G1(7) = 2 + G1(6) + 1 = 3 + G1(6) w1 + F1(8) = 1 + F1(8) = 1 + F1(7) + 1 = 2 + F1(7) = 2 + F1(6) + 1 = 3 + F1(6) 由于G1(6)和F1(6)的值相等，所以w1 + G1(8)和w1 + F1(8)的值相等，贪心法能够正确工作。 综上所述，贪心法对于这个硬币系统能够正确工作。 ///