算法总结系列(二)：贪心法、分治法

算法总结系列(二)：贪心法、分治法

算法2——贪心法、分治法

• 贪心法
• • • 币种统计问题
• 分治法
• • • 快速排序

贪心法

关键词：局部最优、近似

算法描述：
1）定义初始点
2）从初始点出发，找当前点局部最优解
3）以局部最优解为初始点，找新的局部最优解
4）重复步骤（3），直到获得满足要求的解

这里我们先不讲贪心法的使用条件，放到后面讲。
下面先举一个例子——币种统计问题，来描述基础的贪心法流程

币种统计问题

问题描述：
单位给员工发工资，为了保证取款的张数最少，取工资前要统计出所有职工的工资所需各种币值（100，50，20, 10， 5， 2， 1共7种）的张数。

程序求解(python)：

statistic = {'100':0, '50':0, '20':0, '10':0, '5':0, '2':0, '1':0}

bal = 2543

for val in statistic.keys():
	val = int(val)
	num = int(bal / val)
	statistic['{}'.format(val)] = statistic['{}'.format(val)] + num
	bal = bal - num * val

print(statistic)

打印结果：

{'100': 25, '50': 0, '20': 2, '10': 0, '5': 0, '2': 1, '1': 1}

当解决了一个问题后，回过头来思考可以发现新的问题：

1. 什么条件下使用贪心法可以获得最优解？

问题1
问题具有最优子结构、贪心选择性质

最优子结构：问题的最优解包含子问题的最优解，即问题可以划分为子问题，并且可以通过求子问题的最优解递推地获得问题的最优解。

证明最优子结构：首先能不能划分为子问题还是靠直觉 : ( ，然后设规模为n的问题S有最优解E， A 是之前一步已经得到的局部最优解，假设E-{A}不是S-{A}规模中最优的解：即存在 E’是 S-{A}规模中最优的解，且E’ 不等于 E-{A} ， 从而E’并 {A}是S的最优解，显然E’并 {A} 不等于E，与假设E是原问题S的最优解矛盾。所以如果E是S的最优解，则E-{A}也是S-{A}的最优解。以币值问题为例，假设贪心法获得的不是最优解，因为问题要求取款张数最少，则最优解中存在较大的某些币值数量比贪心解多，而贪心法在每一步都是优先选择最大币值，因此最优解中不可能存在较大币值比贪心法多，故假设不成立，最优子结构证毕。这说明问题可以用贪心法获得最优解。

贪心选择：选择当前最优不影响之后的选择

贪心选择我也不知道咋证明（似乎需要用到归纳证明），就举个例子：
同样是上面的币值统计问题，在币值里加入70元，同时要发的工资为140元，你会发现这时贪心法不好使了，最优应该是70* 2，而非100* 1+20* 2。
我的理解就是这个问题需要除最大币值外的所有币值要小于或等于最大币值的1/2，这是这个问题隐含的选择之间互相影响的条件。70*2=140>100，因此不能用贪心法咯。

分治法

关键词：子问题、合并

算法描述：
1）将问题分解为子问题
2）解决子问题
3）合并子问题解

举个栗子：

快速排序

基础流程：
1）设定分界值
2）按照分界值划分数据
3）重复步骤1、2划分分界值两侧数据直到不能划分

程序设计（python）：

def quick_sort(alist, start, end):
    """快速排序"""
    if start >= end:  # 递归的退出条件
        return
    mid = alist[start]  # 设定起始的基准元素
    low = start  # low为序列左边在开始位置的由左向右移动的游标
    high = end  # high为序列右边末尾位置的由右向左移动的游标
    while low < high:
        # 如果low与high未重合，high(右边)指向的元素大于等于基准元素，则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        alist[low] = alist[high]  # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        alist[high] = alist[low]  # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处

    # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
    alist[low] = mid  # 将基准元素放到该位置,
    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low - 1)  # start :0  low -1 原基准元素靠左边一位
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low + 1, end)  # low+1 : 原基准元素靠右一位  end: 最后



if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quick_sort(alist, 0, len(alist) - 1)
    print(alist)

代码来源

在快速排序中，每个基准值两侧的数据就是被划分后的子问题，通过递归地求解子问题，最后将解合并获得最终解，体现了分治法的基本思想。