贪心策略 学习报告

大胆贪心,(不用)小心证明。
——阮行止

简介

定义

贪心算法,本质上来讲不是一种算法,而是一种策略。其基本思路是在题解满足局部最优解将导致全局最优解时,每一次决策考虑且仅考虑当前最优解。

举个例子

就拿天朝RMB面额的设计来讲,仅举这一单位,分别有1元,5元,10元,50元,100元五种面额。
为什么要这样设计呢?
在日常的生活中,我们买东西时就会发现,对于任意一个价格的商品,我们在购买时,要想花费最少张数的RMB,只需永远花费当前小于等于商品面额的货币。这就是一种贪心策略。

例子的证明

我太菜了不会证

使用条件

题意方面

定义中就提到过,要想使用贪心策略,一定要在题解满足局部最优解导致全局最优解。对于简单的贪心,你看题面就知道这是个贪心,而有技巧的贪心则需要自己的猜测与证明

关于局部最优解

局部最优解,即在当前局面看来不考虑后续状态的情况下,结果最优的解。即是当前问题的一个子问题的最优解。

贪心的证明

贪心策略是需要证明的,至于严谨性就看个人对于答案的确信程度和rp

常用的方法

微扰法

个人至今都不是很会的一种方法。
就是先假设一种贪心策略,再对该策略的局面做出所有可能的扰动(如交换相邻的两个元素),然后讨论扰动后的局面是否会造成更优的局面,若是,则原贪心策略被推翻;若对于所有的扰动局面,都有原贪心策略优于微扰后的策略,那么贪心成立。

解集分析法

先枚举出小规模内的局面,若对于该规模问题,所有的解均能由同一种贪心策略取得,那么考虑该策略,扩大问题规模(有点像迭代加深搜索),将该策略取得的解与枚举的解对比,若成立,则策略极有可能成立。
注意这里的极有可能有些毒瘤数据可能刚好违背该策略,所以这是一种不严谨的方法。

数学方法

我们先看个典例

排队打水问题
有n个人排队到r个水龙头去打水,他们装满水桶的时间t1、t2………..tn为整数且各不相等,应如何安排他们的打水顺序才能使他们总共花费的时间最少? 

好像前面两种方法都行不通了?其实我没试过
我没来看一个黑科技

排序不等式

不等式的证明百科上讲的很清楚了,我就把结论挂在这吧:
$$\text{对于两个有序数组:$a_1\le a_2\le a_3\le …\le a_n$及$b_1\le b_2\le b_3\le …\le b_n$:}$$

$$\sum\limits_{i=1}^na_ib_i\ge \sum\limits_{i=1}^na_ib_{j_i}\ge\sum\limits_{i=1}^na_ib_{n+1-i} $$

$${通俗来讲,就是顺序和\ge 乱序和\ge 逆序和}$$

那么,上面的例子就很好解决了吧?

总是规划打水时间最短者先打,再计算总打水时间,就可以得到最优的打水时间。

总结

正如阮行止所说,“太贪心了是要栽跟头的。”,贪心策略固可解决一部分题,但是,如果时时刻刻想着贪心,DP也写贪心,终究是得不到高分的。做人也正是如此吧。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×