vlambda博客
学习文章列表

一看就懂的贪心算法的正确性证明




  编程与算法之美报道  

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

一,问题介绍

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

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

如果可换的硬币的单位是 c 的幂,也就是 c0,c1,... ,ck ,其中整数 c>1,k>=1

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

 

二,找换硬币的贪心策略

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

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

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

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

这里说的某种性质就是:可换的硬币的单位(或者称 面值)是 c 的幂,也就是 c0,c1,... ,ck ,其中整数 c>1,k>=1

下面给出正确性证明。

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

 

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

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

一看就懂的贪心算法的正确性证明

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

why? 假设使用了 c 个(大于c个也一样)面值为 ci 的硬币去找零,那我为什么不用一个 面值为 ci+1 的硬币去找呢?

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

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

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

一看就懂的贪心算法的正确性证明

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

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

一看就懂的贪心算法的正确性证明

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

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

一看就懂的贪心算法的正确性证明

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

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

因此有:

一看就懂的贪心算法的正确性证明

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

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

一看就懂的贪心算法的正确性证明

 

一看就懂的贪心算法的正确性证明

 

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

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

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

一看就懂的贪心算法的正确性证明              从而得到了一个更优的问题。

 

扫码加入Python算法学习群,备注
“学校、机构+昵称”
未按要求备注不予通过哦

  
    
    
  

往期精选