贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

 

贪心算法的要素

贪心选择

贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

最优子结构

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题 。

 

基本思路

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 [3]  。

过程

1. 建立数学模型来描述问题；

2. 把求解的问题分成若干个子问题；

3. 对每一子问题求解，得到子问题的局部最优解；

4. 把子问题的解局部最优解合成原来解问题的一个解。

 

算法特性

贪婪算法可解决的问题通常大部分都有如下的特性：

• 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

• 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

• 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

• 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

• 最后，目标函数给出解的值。

• 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

下面来用Python实现几道例题

1. 分糖果(leetcode455) 

题目：已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s>=某个孩子的需求因子g时，代表该糖果可以满足该孩子，求使用这些糖果，最多能满足多少孩子（注意，某个孩子最多只能用1个糖果满足）

思考：

当某个孩子可以被多个糖果满足时，是否需要优先用某个糖果满足这个孩子？
当某个糖果可以满足多个孩子时，是否需要优先满足某个孩子？
贪心规律是什么？

贪心规律：

某个糖果如果不能满足某个孩子，则该糖果也一定不能满足需求因子更大的孩子

某个孩子可以用更小的糖果满足，则没必要用更大糖果满足，因为可以保留更大的糖果满足需求因子更大的孩子
孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，可以得到正确的结果(因为我们追求更多的孩子被满足，所以用一个糖果满足需求因子较小或较大的孩子都是一样的)。
算法设计：

(1)对需求因子数组g和糖果大小数组s进行从小到大的排序
(2)按照从小到大的顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次，只有尝试成功时，换下一个孩子尝试，直到发现没更多的孩子或者没有更多的糖果，循环结束。

class Solution:
    def findContentChild(self,g,s):
        g = sorted(g)
        s = sorted(s)
        child = 0
        cookie = 0
        while child < len(g) and cookie < len(s):
            if g[child] <= s[cookie]:
                child +=1
            cookie+=1
        return child
if __name__ =="__main__":
    g = [5,10,2,9,15,9]
    s = [6,1,20,3,8]
    S = Solution()
    result = S.findContentChild(g,s)
    print(result)

 

2. 摇摆序列(leetcode376) 

题目：一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列呗成为摇摆序列，一个小于2个元素的序列直接为摇摆序列，给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度。 
例如： 
序列[1,7,4,9,2,5],相邻元素的差(6,-3,5,-7,3),该序列为摇摆序列 
序列[1,4,7,2,5]相差(3,3,-5,3)不是摇摆序列

思考与分析： 

[1,17,5,10,13,15,10,5,16,8]，整体不是摇摆序列，但是我们观察该序列的前6位：[1,17,5,10,13,15…];5,10,13,15部分为上升段，其中有三个子序列是摇摆序列： 
[1,17,5,10….] 
[1,17,5,13,…] 
[1,17,5,15…..] 
在不清楚原始序列的7为是什么的情况下，只看前6位，摇摆子系列的第四位从10，13，15中选择一个数，我们应该选择那一个？

应该选择使得摇摆子序列长度更长的数，所以应该是15，这样遇到比他小的数的可能性就会大一点，按照这种思路总结出贪心规律

贪心规律：

 
当序列有一段连续的递增(或递减)时，为形成摇摆子序列，我们只需要保留这段连续的递增(或递减)的首尾元素，这样更有可能使得尾部的后一个元素成为摇摆子序列的下一个元素。

 

算法设计：

设置最长摇摆子序列长度为max_length，从头到尾扫描原始序列，这个过程中设置三种状态，即起始、上升、下降；不同的状态中，根据当前数字和前一个数字的比较结果进行累加max_length计算或者状态切换 

 

class Solution:
    def maxlength(self, nums):
        if len(nums) < 2:
            return len(nums)
        BEGIN = 0
        UP = 1
        DOWN = 2
        STATE = BEGIN
        max_length = 1
        vision = [UP, BEGIN, DOWN]
        for i in range(1, len(nums)):

            if STATE == 0:
                if nums[i - 1] < nums[i]:
                    STATE = 1
                    max_length += 1
                elif nums[i - 1] > nums[i]:
                    STATE = 2
                    max_length += 1
            if STATE == 1:
                if nums[i - 1] > nums[i]:
                    STATE = 2
                    max_length += 1

            if STATE == 2:
                if nums[i - 1] < nums[i]:
                    STATE = 1
                    max_length += 1
        return max_length


if __name__ == "__main__":
    S = Solution()
    g = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
    result = S.maxlength(g)
    print(result)

 

3. 移除K个数字(leetcode402) 

题目：已知一个使用字符串表示非负整数num，将num中的k个数字移除，求移除k个数字后，可以获得的最小的可能的新数字(num不会以0开头，num长度小于10002)

例如：输入：num = “1432219”,k=3 
在去掉3个数字后得到的很多可能里，如1432，4322，2219，1219。。。。；去掉数字4、3、2、得到的1219最小

思考与分析： 

一个长度为n的数字，去掉k个数字，可以有多少种可能？C(k,n)=n!/(n−k)!∗k!C(k,n)=n!/(n−k)!∗k!种可能 
所以用枚举法肯定是不可能的。 
若去掉某一位数字，为了使得到的新数字最小，需要尽可能让得到的新数字优先最高位最小，其次次位最小，再其次第三位最小。。。。

例如：一个四位数 “1。。。”，一定比任何“9.。。。”小。 
一个四位数若最高位确定，如“51。。”一定比任何“59。。”、“57。。”小。

贪心规律：

 
从高位向地位遍历，如果对应的数字大于下一位数字，则把该位数字去掉，得到的数字最小。

算法设计： 
使用栈存储最终结果或删除工作，从高位向低位遍历num，如果遍历的数字大于栈顶元素，则将该数字push入栈，如果小于栈顶元素则进行pop弹栈，直到栈为空或不能再删除数字(k==0)或栈顶小于当前元素为止。最终栈中从栈底到栈顶存储的数字，即为结果。

 

下面我们来看看这几个问题：

当所有数字都扫描完成后，K仍然>0，应该做怎么样的处理？
当数字中有0出现时，应该有怎么样的特殊处理？
如何将最后结果存储为字符串并返回？
 

class Solution:
    def removeknums(self,nums,k):
        s =  []
        nums = list(map(int, nums))
        for i in range(len(nums)):
            number = int(nums[i])
            while len(s)!= 0 and s[len(s)-1]> number and k >0:
                s.pop(-1)
                k -=1
            if number!=0 or len(s)!=0:
                s.append(number)
        while len(s) !=0 and k>0:
            s.pop(-1)
            k-=1
        result = ""

        result = ''.join(str(i) for i in s)

        return result
if __name__ == "__main__":
    S = Solution()
    print(S.removeknums("1432219",2))

4.圣诞节发糖果

    圣诞节来临了，在城市A中，圣诞老人准备分发糖果。现在有多箱不同的糖果，每一种糖果都有自己的价值和重量。每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果。请问圣诞老人最多能带走多大价值的糖果。

输入数据：

    输入的第一行由两个部分组成，分别为糖果箱数正整数n(1<=n<=100)，驯鹿能承受的最大重量正整数w(0<w<10000)；其余n行每行对应一箱糖果，由两部分正整数v和w组成，分别为一箱糖果的价值和重量。

输出要求：

    输出圣诞老人能带走的糖果的最大总价值，保留一位小数，输出为一行。

输出样例：

　　4     15

　　100  4

　　412  8

　　266  7

　　591  2

输出样例:

　　1193.0

注：此处并没有按照这样的格式进行输入。

 

# encoding:utf-8
from __future__ import division

input_a = raw_input(u'箱数:')
input_b = raw_input(u'最大承受重量:')

list_c = []
list_z = []

for i in range(1,int(input_a)+1):
    input_c = raw_input('第'+str(i)+'箱的总价值:')
    input_d = raw_input('第'+str(i)+'箱的重量:')
    avg = round(int(input_c)/int(input_d),1)#每一箱，重量为1的价值
    list_c.append(avg)#添加到列表，用于之后做比较
    list_z.append([int(input_d),avg,0])#此处列表中添加列表，中间的列表一个存放总重量，第二个存放单位价值，第三个存放是否该物品已被取走

list_c.sort(reverse=True) # 降序排序
sum =[0,0]# 用于存放取走的总重量，第一个参数是取走的重量，第二个是超出前的备份
num =0
ji = 0

for i in range(len(list_c)):
    for k in range(len(list_z)):
        if ji == 0:#做是否超出马车最大承受量的标记，未超出为0
            if (list_c[i] == list_z[k][1]) and (list_z[k][2]==0):
                sum[1] = sum[0]#备份
                sum[0] = sum[0] + list_z[k][0]#取走的重量
                v = list_z[k][0]#取走的重量
                if sum[0] > int(input_b):#如果所有取走的重量超出马车的重量，就依次减少一单元的重量
                    ji = 1#超出为1
                    t= list_z[k][0]
                    while True:#依次减去单位1的重量
                        z = sum[1] + t#使用备份进行判断，此时取走的数量已经大于最大承受量了
                        if z <= int(input_b):
                            break
                        t = t-1
                    v=t#等于最大承受量时，价值较大的一件物品应取走的数量
                    sum[0]=sum[1]#从备份恢复
                    sum[0] = sum[0] + t#此时为真正的取走数量
                num = list_c[i]*v + num#总价值
                list_z[k][2] = 1#取走的标记
print u'能带走的糖果的最大价值为:',num

5.找零钱问题

假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时，如果 需要找零钱， 收银员希望将最少的硬币数找给顾客。那么，给定 需要找的零钱数目，如何求得最少的硬币数呢？

def main():
    d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币面值
    d_num = [] # 存储每种硬币的数量
    s = 0
    # 拥有的零钱总和
    temp = input('请输入每种零钱的数量：')
    d_num0 = temp.split(" ")

    for i in range(0, len(d_num0)):
        d_num.append(int(d_num0[i]))
        s += d[i] * d_num[i] # 计算出收银员拥有多少钱

    sum = float(input("请输入需要找的零钱:"))

    if sum > s:
        # 当输入的总金额比收银员的总金额多时，无法进行找零
        print("数据有错")
        return 0

    s = s - sum
    # 要想用的钱币数量最少，那么需要利用所有面值大的钱币，因此从数组的面值大的元素开始遍历
    i = 6
    while i >= 0:
        if sum >= d[i]:
            n = round(int(sum / d[i]))
            if n >= d_num[i]:
                n = d_num[i]  # 更新n
            sum -= n * d[i] # 贪心的关键步骤，令sum动态的改变，
            print("用了%d个%f元硬币"%(n, d[i]))
        i -= 1

if __name__ == "__main__":
    main()

6.求最大子数组之和问题：给定一个整数数组（数组元素有负有正），求其连续子数组之和的最大值

 

# -*- coding:utf-8 -*-
def main():
    s = [12,-4,32,-36,12,6,-6]
    print("定义的数组为：",s)
    s_max, s_sum = 0, 0
    for i in range(len(s)):
        s_sum += s[i]
        if s_sum >= s_max:
            s_max = s_sum # 不断更新迭代s_max的值，尽可能的令其最大
        elif s_sum < 0:
            s_sum = 0
    print("最大子数组和为：",s_max)

if __name__ == "__main__":
    main()

 

7.一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。

 

# 设汽车加满油后可行驶n公里，且旅途中有k个加油站

def greedy():
    n = 100
    k = 5
    d = [50,80,39,60,40,32]
    # 表示加油站之间的距离
    num = 0
    # 表示加油次数
    for i in range(k):
        if d[i] > n:
            print('no solution')
            # 如果距离中得到任何一个数值大于n 则无法计算
            return 

    i, s = 0, 0
    # 利用s进行迭代
    while i <= k:
        s += d[i]
        if s >= n:
            # 当局部和大于n时则局部和更新为当前距离
            s = d[i]
            # 贪心意在令每一次加满油之后跑尽可能多的距离
            num += 1
        i += 1
    print(num)

if __name__ == '__main__':
    greedy()