最“简单”的算法—

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学就知道怎么贪。有人说贪心算法是最复杂的算法，原因也很简单：这世上会贪的人太多了，那轮到你我的份？
——By CSDN@lloil

贪心算法简介

什么是贪心算法

贪心算法（greedy algorithm，又称贪婪算法） 是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
——By 百度百科·贪心算法

基本要素

1.贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择，即贪心选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解

2.最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析

基本思路

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当达到算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

不能保证求得的最后解是最佳的；

一般用来求最大或最小解问题；

只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
从问题的某一初始解出发:

1
2
3


while 能朝给定总目标前进一步:
　　 求出可行解的一个解元素
由所有解元素组合成问题的一个可行解

一道简单的例题

题目如下

原题：拼座椅

题目描述

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。
同学们在教室中坐成了 M 行 N 列，坐在第 i 行第 j 列的同学的位置是（i，j）（i，j），为了方便同学们进出，在教室中设置了 K 条横向的通道，LL 条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。

输入描述:

第一行，有 5 各用空格隔开的整数，分别是 M，N，K，L，D（2 ≤ N，M ≤ 1000，0 ≤ K < M，0 ≤ L < N，D ≤ 2000）。
接下来 D 行，每行有 4 个用空格隔开的整数，第 i 行的 4 个整数 X_i，Y_i，P_i，Q_i，表示坐在位置 (X_i, Y_i) 与 (P_i, Q_i) 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。输入数据保证最优方案的唯一性。

输出描述

共两行：
第一行包含 K 个整数， a_1 a_2 … a_k，表示第 a_1 行和 a_1 + 1 行之间、第 a_2 行和第 a_2 + 1 行之间、…、第 a_k 行和第 a_k + 1 行之间要开辟通道，其中 a_i < a_i + 1 ，每两个整数之间用空格隔开（行尾没有空格）。
第二行包含 L 个整数， b_1 b_2 … b_k，表示第 b_1 列和 b_1 + 1 行之间、第 b_2 行和第 b_2 + 1 行之间、…、第 b_l 行和第 b_l + 1 行之间要开辟通道，其中 b_l < b_l + 1，每两个整数之间用空格隔开（行尾没有空格）。

示例

输入

输出

说明

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

题目分析

这是一道典型的贪心算法题。要满足交头接耳的学生对数最少，只需选择能分开学生对数最多的行和列即可。
~~有人把这道题比喻成切虫子：有若干条长度为 2 的虫子，怎么切才能使切死的虫子数最多（莉格露表示强烈谴责）~~

然而即便是这么简单的题，也有不少 难点/陷阱

注意输出：行尾没有空格
升序输出
重点(针对 C 语言)：如何在一个数组中求值前 k 大的值（不改变下标）
冒泡排序

关于第三点的说明

如：求int arr[] = {1, 7, 6, 8, 32}中第一大的值、第二大的值、第三大的值……

方法：

在外面定义int max_num = 0，然后遍历数组，比max_num大的值就将它赋给max_num，即获取最大值

再次遍历数组，将第一个数组值等于max_num的值置为-1，这样下一次求得的是第二大的值

重复步骤1、2，直至求得所有待求值

理论成立，上 ~ 代 ~ 码 ~

源代码

C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


#include <stdio.h>
void bubble_sort(int a[], int size)
{
    int i, j, temp;
    for (i=0; i<size-1; i++)
    {
        for (j=0; j<size-i-1; j++)
        {
            if (a[j] > a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}
void get_result(int a[], int n, int k)
{
    int i=1, j, max_num, max[k];
    while (i <= k)  /* 获取第 i 大值 */
    {
        max_num = 0;
        for (j=0; j<n; j++)
        {
            if (a[j] > max_num)
            {
                max_num = a[j];
                max[k-i] = j+1;
            }
        }
        a[max[k-i]-1] = -1;  /* 第三点(2.2.1) 2. */
        i++;
    }
    bubble_sort(max, k);  /* 冒泡排序以便升序输出 */
    for (j=0; j<k; j++)
    {
        if (j != k-1) printf("%d ", max[j]);
        else printf("%d\n", max[j]);
    }
}
int main()
{
    int m, n, k, l, d, i;
    scanf("%d %d %d %d %d", &m, &n, &k, &l, &d);
    int x[d], y[d], p[d], q[d], ak[m], bl[n];
    for (i=0; i<m; i++)
    {
        ak[i] = 0;
    }
    for (i=0; i<n; i++)
    {
        bl[i] = 0;
    }
    for (i=0; i<d; i++)
    {
        scanf("%d %d %d %d", &x[i], &y[i], &p[i], &q[i]);
    }
    for (i=0; i<d; i++)
    {
        if (y[i] == q[i])
        {
            if (x[i] > p[i]) ak[p[i]-1]++;
            else ak[x[i]-1]++;
        }
        else
        {
            if (y[i] > q[i]) bl[q[i]-1]++;
            else bl[y[i]-1]++;
        }
    }
    get_result(ak, m, k);
    get_result(bl, n, l);
    return 0;
}

Python

参考：@comter

Python 的map()、count()和sort()等函数可以省不少功夫
这就是我更喜欢 Python 的原因之一（笑）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def get_result(lis, q):
    """冒泡排序"""
    result_list = list(set(lis))        
    for i in range(len(result_list)):
        for j in range(len(result_list) - i - 1):
            if lis.count(result_list[j]) < lis.count(result_list[j+1]):
                result_list[j], result_list[j+1] = result_list[j+1], result_list[j]
    result_list = result_list[:q]
    result_list.sort()  # 还是Python香（
    return ' '.join(map(str, result_list))

    
m, n, k, l, d = map(int, input().split())  # map()会根据提供的函数对指定序列做映射
ak, bl = [], [] 
for i in range(d):
    x, y, p, q = map(int, input().split())
    if x == p:
        bl.append(min(y, q))
    else:
        ak.append(min(x, p))
print(get_result(ak, k))
print(get_result(bl, l))

~~才二十几行代码就解决了 C 七十几行代码才解决的问题~~

总结

算法不愧是编程的灵魂……
这才是编程的浪漫啊！~~（因解题时间过长理智丧失ing…）~~ 妹红敲代码.jpg

参考文献

[1]贪心算法详解
[2]百度百科·贪心算法

To Be Continue…

关于贪心算法，我只是学了点皮毛而已，以后还会在这里更新更加deep♂dark的用法