移山之道

哈哈，从投票可以看出大家对游戏的喜爱：）

个人觉得这本书最美的是它传达的思想，读完以后，我不禁对朋友感慨——“这些年写程序，一直自认为是精益求精，追求型式和效率的统一。直到读了《编程之美》后，才发现还远远不够...”

《编程之美》是我算法的启蒙老师，从此开始了一个新的旅程，我开始学习它的方式思考问题、写程序、写博客...

我开始试图在图书馆查找类似的，简洁、精妙能学到东西的书，发现确实不好找...

个人觉得书中的题目都很美，虽然我喜欢的和大家有点不同，但是依照“长尾”来看，不是80％人喜欢的题目也很有价值的。

很久没来了，没想到关心老师还一直在写博客呀，果然是笔耕不辍呀！

《编程之美》----1.4买书问题。

对买书问题有变形的贪心算法证明：

       符号：【3】y3表示享受3卷的折扣y3次，即一共有3*y3本书。其他类推。

       折扣条件 【5】 25% 【4】20%  【3】10% 【2】5% 【1】0%

 算法如下：

1. 对给定要买的书籍书卷的数量按小到大排序，不妨设书卷（A,B,C,D,E）的各自购买数量为（x1,x2,x3,x4,x5）(x1<=x2<=x3<=x4<=x5).

2. 按照贪心算法得到有 【5】本书享受折扣 x1 次，【4】本享受x2-x1次, 【3】有x3-x2次，【2】有x4-x3次，【1】有x5-x4次。

3. 享受【5】本折扣{A,B,C,D,E}和【3】任意折扣{B,D,E}的总是能分拆成两份【4】折扣{A,B,D,E},{B,C,D,E}。故将第2步中所得的【5】x1，【3】x3-x2，合并入【4】折扣中.     {如x3-x2<=x1则新的折扣布局为【5】x1-x3+x2,【4】x2-x1+2*(x3-x2),【3】0,【2】x4-x3,【1】x5-x4.}

4. 按上述计算全部折扣。

 算法证明：设要购买y本书，并且按最优折扣有【5】y5,【4】y4,【3】y3,【2】y2,【1】y1。现在来考察最优折扣的解得结构。

         因为【5】+【3】总能拆分成【4】+【4】并且【4】+【4】=1.6>【5】+【3】.故在最优折扣中y5和y3必然有一个为0(或两个都为0)

       现在分情况讨论

y5=0.考察，【5】y5=0,【4】y4,【3】y3,【2】y2,【1】y1。                                          【1】y1的集合中卷数必然只有一种（若有两重卷书则够成【2】折扣），不妨设其为卷E。                                                      

【2】y2的集合中卷数必然只有两种（【3】+【1】>【2】+【2】），并且其中一种为卷E。不妨设为D,E。

同理：【3】y3集合中卷数种类只有三种，并包含D,E。不妨设为C,D,E.

【4】中可有五种卷，但其只能是{A,C,D,E},{B,C,D,E}类型折扣。若有不包含{CDE}型的折扣（如ABCD）则可与【3】中的CDE合并分拆成【5】+【2】>【4】+【3】.

这样就得到了：

  A B C D E

【5】 0 0 0 0 0

【4】 XA XB y4 y4 y4

【3】 y3 y3 y3

【2】 y2 y2

【1】 y1

       {A,B,C,D,E}的数量为（XA,XB,y3+y4,y3+y4+y2,y4+y3+y2+y1）, 其中XA+XB=y4.

       可知当书卷C数量y3+y4>= XA+XB=y4书卷A+B的数量时，用上述变形的贪心算法恰好得到最优折扣的解。

当y5!=0,y3=0时候：考察，【5】y5,【4】y4,【3】y3=0,【2】y2,【1】y1。的结构。

【1】y1的集合中卷数必然只有一种（若有两重卷书则够成【2】折扣），不妨设其为卷E。                                                      

【2】y2的集合中卷数必然只有两种（【3】+【1】>【2】+【2】），并且其中一种为卷E。不妨设为D,E。

【3】y3=0。

【4】y4的集合中折扣类型必然都包含{D,E}。故为Z1{BCDE}，Z2{ACDE}，Z3{ABDE}，其中Z1+Z2+Z3=y4。

现在证明【4】中只能有两种折扣类型。（反证法）

若有三种 则有{BCDE}+{ACDE}+{ABDE}={ABCDE}+{ABCDE}+{DE}

但是折扣模型【4】+【4】+【4】<【5】+【5】+【2】所以与最优解矛盾。

故【4】y4中的折扣类型最多只能有两种。不妨设其为Z1{BCDE}，Z2{ACDE}

其中Z1+Z2=y4.    

【5】y5的集合为{A,B,C,D,E}。

现在有

  A B C D E

【5】 y5 y5 y5 y5 y5

【4】 Z1 Z2 y4 y4 y4

【3】 0 0 0

【2】 y2 y2

【1】 y1

       {A,B,C,D,E}的数量分别为（y5+Z1,y5+Z2,y5+y4,y5+y4+y2,y4+y5+y2+y1）, 其中

       Z1+Z2=y4。当卷A+卷B数量y5+Z1+y5+Z2=2*y5+y4>y5+y4卷C的数量时候，最优折扣模型也可由上述变形的 贪心算法得到。

  综合上述，算法正确！

   代码：(假设数组a已经按小到大排序)

      float Optimize_ discount（int a[],int n=5）

            {

              If(a[0]>=a[2]-a[1])

{

return (a[0]+a[1]-a[2])*5*25%+(a[1]-a[0]+2a[2]-2a[1])*20%+(a[3]-a[2])*5%; }

              else

                 { return  (a[1]-a[0]+2*a[0])*20%+(a[2]-a[1]-a[0])*10%+(a[3]-a[2])*5%;}

            }

@ cwzw

谢谢你的反馈， 我们要好好看看。