vlambda博客
学习文章列表

---

  编程与算法之美报道  

链接：https://www.cnblogs.com/hapjin/p/5575112.html

一，问题介绍

最近一直在看贪心算法的正确性证明（如何证明贪心算法获得的解一定是最优解），感觉“剪枝”技巧用得比较多。再看了下《算法导论》中贪心算法一章里面的一个练习---找换硬币问题。这个问题对于某些 面值的硬币 是有最优解的，故记录下其中的一些证明思路。

考虑用最少的硬币数 来找 n 分钱的问题，假设每个硬币的值都是整数。

如果可换的硬币的单位是 c 的幂，也就是 c⁰，c¹，... ，c^k ,其中整数 c>1，k>=1

证明贪心算法总可以产生一个最优解。

二，找换硬币的贪心策略

这里的贪心策略很容易想到：总是优先选择 大面值的硬币 去找。比如，现有 1分、5分、25分的硬币可用来找钱，现在我们需要找 n=32分 的零钱，如何找？

优先选择大面值的嘛，那就是先选 25分；选完之后，还要找32-25=7，那就再选5分的，最终再先2个1分的。即可。

这里：32=25+5+1+1，一共用了4枚硬币。那么，问题来了！！！还有没有其他策略 只需要 3 枚硬币？或者更少的硬币？

这就需要证明贪心策略 有没有 最优解了？对于这个问题而言，如果用来找换的硬币的 面值 满足某种性质，该贪心策略是有最优解的。

这里说的某种性质就是：可换的硬币的单位（或者称 面值）是 c 的幂，也就是 c⁰，c¹，... ，c^k ,其中整数 c>1，k>=1

下面给出正确性证明。

这里需要强调一点： 硬币面值满足上面的性质时贪心算法一定能产生最优解，但是不满足时，也有可能有最优解。比如，面值为1，5，10，20，50，100时，贪心找零也一定有最优解。

三，找换硬币的贪心算法的正确性证明

在进行证明之前，先提一个性质：对于最优解而言，如果使用了面值为 cⁱ 的硬币去找零，那么 cⁱ 最多只能使用 c-1 个。

因为我们的目标是使用 最少数目的硬币，对于最优解而言，如果使用了面值为 cⁱ 的硬币去找零，那么 cⁱ 最多只能使用 c-1 个。

why? 假设使用了 c 个(大于c个也一样)面值为 cⁱ 的硬币去找零，那我为什么不用一个 面值为 cⁱ⁺¹ 的硬币去找呢？

这样，我就可以用更少的硬币数啊(c>1)。所以说，在最优解里面，如果使用了面值为 cⁱ 的硬币去找零，那么 面值为cⁱ 的硬币 最多只能使用 c-1 个。

OK，下面再次用到剪枝的思想来证明贪心选择的正确性了。

总体思路是：先考察一个最优解，然后证明可对该解进行修改，使其采用贪心选择，这个选择将原问题变成一个相似的、但是“更小”的问题。（这里说的“更小”是一种抽象，并不是具体意义上的更小）

k 是可找换的硬币的种类数，n 是需要找换的价值，a(i)表示使用多少个 面值为 cⁱ 的硬币。假设硬币已经按面值从小到大排序。

对于贪心选择而言，我们一定会选择面值为 c^j 的硬币，因为：我们的贪心策略就是总是优先选择 面值最大的硬币。

我们的目标是证明，对于所有的非贪心选择而言，它们都不可能产生最优解。

对于非贪心选择，是不会选择 面值为 c^j (or higher)的硬币的。非贪心选择使用的硬币如下：

其中，a(i)表示使用了 a(i)个 面值为 cⁱ 的硬币，总数之和是n。别忘了，n 就是需要找零的数目

而对于贪心选择而言，如果面值为 c^j 的硬币可用（当 n>=c^j 时），我们是优先使用 面值为 c^j 的硬币的。

因此有：

这说明，在面值为 c^j 的硬币 可用的情况下，换句话说：在 c^j <=n 的情况下，非贪心选择没有使用 c^j 嘛。(选择了的话，那就是贪心选择了嘛...~)

 这里就会有矛盾了，根据前面提到的性质：有， a(i) <= c-1

从而，证明了贪心选择的正确性。

再来理解下它：总体思路是：先考察一个最优解，然后证明可对该解进行修改，使其采用贪心选择，这个选择将原问题变成一个相似的、但是“更小”的问题。（这里说的“更小”是一种抽象，并不是具体意义上的更小）

这里的最优解是：非贪心选择下的某个最优解，然后剪枝：将非贪心选择下的某个元素去掉，然后添入贪心选择的那个元素。其实就是下面的这个公式。

              从而得到了一个更优的问题。

  
    
    
  

   
     
     
   
 
    
 
     
 
      
 
       
 
        
往期精选