Greedy Algorithm

定义

贪心算法，是指在对问题求解时，总是做出再当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是某种意义上的局部最优解。贪心算法没有固定算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

基本思路

1. 建立数学模型来描述问题
2. 把求解的问题分成若干个子问题
3. 对每一子问题求解，得到子问题的局部最优解
4. 把子问题的解局部最优解合成原来解问题的一个解

适用的问题

局部最优策略能导致产生全局最优解

最小生成树问题

给定一个无向联通带权图G(V,E). G中的每一条边\(E_i\)权值为\(w_i\)。如果G的子图G'是一个包含G中所有顶点的子图，那么G'称为G的最小生成树，如果G'的边的权值最小.

Kruskal算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。

1. 将图G看做一个森林，每个顶点为一棵独立的树
2. 将所有的边加入集合S，即一开始S = E
3. 从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E'
4. 重复(3)直到所有点属于同一棵树，边集E'就是一棵最小生成树

class UnionFind():
    def __init__(self,items):
        self.parent = {item:item for item in items}

    def get_root(self, i):
        while i != self.parent[i]:
            i = self.parent[i]
        return i

    def is_connected(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def union(self, i, j):
        i_root = self.get_root(i)
        j_root = self.get_root(j)
        self.parent[i_root] = j_root


def kruskal(G):
    nodes = list(G.keys())
    uf = UnionFind(nodes)

    res_deges = set()
    res_weight = 0

    edges = set()
    for node_1 in G:
        for node_2 in G[node_1]:
            if node_1 < node_2:
                edges.add((node_1,node_2, G[node_1][node_2]))
            else:
                edges.add((node_2,node_1, G[node_1][node_2]))
    edges = list(edges)
    edges.sort(key = lambda edge: edge[-1])
    
    for edge in edges:
        node_1,node_2,weight = edge
        if not uf.is_connected(node_1,node_2):
            uf.union(node_1,node_2)
            res_deges.add(edge)
            res_weight += weight

    return res_deges,res_weight



if __name__ == '__main__':
    graph = {'A':{'B':7,'D':5},
             'B':{'A':7,'C':8,'D':9,'E':7},
             'C':{'B':8,'E':5},
             'D':{'A':5,'B':9,'E':15,'F':6},
             'E':{'B':7,'C':5,'D':15,'F':8,'G':9},
             'F':{'D':6,'E':8,'G':11},
             'G':{'E':9,'F':11}
             }
    edges, weight = kruskal(graph)
    print(edges)
    print(weight)

Prim算法

1. 以某一个点开始，寻找当前该点可以访问的所有的边；
2. 在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
3. 寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
4. 此时由所有边构成的树即为最小生成树。

def prim(graph, root):
    
    nodes = list(graph)
    nodes.remove(root)
    visited = [root]
    edges = set()
    weight = 0

    while nodes:
        distance = float('inf') 
        for s in visited:
            for d in graph[s]:
                if d in visited or s == d:
                    continue
                if graph[s][d] < distance:
                    distance = graph[s][d]
                    node_1 = s
                    node_2 = d
        edges.add((node_1,node_2,graph[node_1][node_2]))
        weight += graph[node_1][node_2]
        visited.append(node_2)
        nodes.remove(node_2)
    
    return edges,weight



if __name__ == '__main__':
    graph = {'A':{'B':7,'D':5},
             'B':{'A':7,'C':8,'D':9,'E':7},
             'C':{'B':8,'E':5},
             'D':{'A':5,'B':9,'E':15,'F':6},
             'E':{'B':7,'C':5,'D':15,'F':8,'G':9},
             'F':{'D':6,'E':8,'G':11},
             'G':{'E':9,'F':11}
             }

    edges, weight = prim(graph,'A')
    print(edges)
    print(weight)

leetcode 455 Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive. 
You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

因为最小的孩子最容易得到满足，因此先满足最小孩子。给一个孩子的饼干应当尽量小又能满足该孩子，这样大饼干就能拿来给满足度比较大的孩子。 假设在某次选择中，贪心策略选择给第 i 个孩子分配第 m 个饼干，并且第 i 个孩子满足度最小，第 m 个饼干为可以满足第 i 个孩子的最小饼干，利用贪心策略最终可以满足 k 个孩子。假设最优策略在这次选择中给 i 个孩子分配第 n 个饼干，并且这个饼干大于第 m 个饼干。我们发现使用第 m 个饼干去替代第 n 个饼干完全不影响后续的结果，因此不存在比贪心策略更优的策略，即贪心策略就是最优策略。

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        res = 0; i = 0; j = 0
        g.sort()
        s.sort()
        
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                res += 1
                i+=1
            j+=1
        
        return res