算法-贪心算法 - 日勿の部落格

基本思想#

当一个问题具有最优子结构性质时，可以用动态规划法求解。但有时会有更有效的方法，例如贪心算法。顾名思义，贪心算法总是做出当前看来最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，我们希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。如图的单源最短路径问题、最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。

活动安排问题#

问题定义#

设有 $n$ 个活动的集合 $E=\{1,2,...,n\}$ ，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 $s_i$ 和一个结束时间 $f_i$ ，且 $s_i \lt f_i$ 。如果选择了活动 $i$ ，则它在半开时间区间 $[s_i\ f_i)$ 内占用资源。若区间 $[s_i,\ f_i)$ 与区间 $[s_j,\ f_j)$ 不相交，则称活动 $i$ 与活动 $j$ 是相容的。也就是说，当 $s_i \geq f_j$ 或 $s_j \geq f_i$ 时，活动 $i$ 与活动 $j$ 相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

算法思想#

首先对活动按照结束时间进行排序。然后，我们选择第一个活动，并从第二个活动开始遍历，如果当前活动的开始时间大于等于前一个所选活动的结束时间，则选择该活动，并输出其信息。

由于算法每次总是选择具有最早完成时间的相容活动。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

代码实现#

1
// 活动结构体
2
typedef struct {
3
    int start;
4
    int finish;
5
} Activity;
6

7
// 比较函数，用于排序活动
8
int compare(const void* a, const void* b) {
9
    // 类型转换的优先级低，因此需要加两重括号
10
    return ((Activity*)a)->finish - ((Activity*)b)->finish;
11
}
12

13
// 贪心算法解决活动安排问题
14
void activityScheduling(Activity activities[], int n) {
15

16
    // 按照结束时间对活动进行排序
17
    qsort(activities, n, sizeof(Activity), compare);
18

19
    // 输出排序后的activities数组
20
    printf("Sorted activities, format is 'id: (start time, end time)': \n");
21
    for (int i = 0; i < n; i++) {
22
        printf("%d: (%d, %d)\n", i + 1, activities[i].start, activities[i].finish);
23
    }
24

25
    printf("selected activity, format is 'id: (start time, end time)': \n");
26

27
    // 选择第一个活动
28
    int i = 0;
29
    printf("%d: (%d, %d)\n", i + 1, activities[i].start, activities[i].finish);
30

31
    // 选择其他活动
32
    for (int j = 1; j < n; j++) {
33
        if (activities[j].start >= activities[i].finish) {  // 活动j与活动i不冲突
34
            i = j;  // 选择活动j
35
            printf("%d: (%d, %d)\n", i + 1, activities[i].start, activities[i].finish);
36
        }
37
    }
38
}

全局最优解证明#

贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解。这个结论可以用数学归纳法证明。

假设活动集合 $E=\{1,2,...,n\}$ 是一个已经以结束时间非递减顺序排好的集合，那么活动 1 的完成时间是最早的。

首先证明存在第一个活动就是贪心算法选择的活动的最优解。假设 $A \subseteq E$ 是一个最优解，且 $A$ 中的活动也是以结束时间非递减顺序排好的。假设 $A$ 中的第一个活动是 $k$ ：

当 $k=1$ 时，最优解的第一个活动就是贪心选择的活动。
当 $k \geq 1$ 时，假设 $B=A-\{k\}\ \cup \{1\}$ ，则 $B$ 也是相容的，并且个数与 $A$ 相同，所以 $B$ 也是最优的，且也是以贪心选择活动 1 开始的。

{% note info modern %} $B=A-\{k\}\ \cup \{1\}$ 就是从 $A$ 中把第一个活动从 $k$ 替换为 1。显然，1 作为结束时间最早的活动，你一个结束的不比我早的 $k$ 放进去都相容，那换成 1 必定也相容。 {% endnote %}

综上，总是存在以贪心选择开始的最优解。

在选择了活动 1 后，剩下的任务就是从 $E' = E-\{1\}$ 中继续选择活动。若 $A$ 是最优解，则 $A'=A-\{1\}$ 也是 $E'$ 的最优解。下面给出证明。

假设能找到 $E'$ 的另一个最优解 $B'$ ，其包含的活动数量比 $A'$ 更多，那就八达鸟了。如果说最优解 $A$ 里包含 $m$ 个活动，那么 $A'$ 比它少一个，也就是 $m-1$ 个。那作为比 $A'$ 数量更多的 $B'$ ，至少得是 $m$ 个吧，并且这 $m$ 个活动里不包括活动 1（因为活动 1 已经被选择了，all right？）。还是那个道理，活动 1 作为结束最早的活动，把它加入 $B'$ 显然也是相容的，此时 $B'$ 至少包含 $m+1$ 个活动。显然，最优解也才 $m$ 个，那 $B'$ 直接荣登最优解，这与假设矛盾。

综上，在活动安排问题中，贪心算法得出的解就是全局最优解。

背包问题#

问题定义#

给定 $n$ 种物品和一个背包。物品 $i$ 的重量是 $w_i$ ，其价值为 $v_i$ ，背包的容量为 $c$ 。假设装入物品时，可以选择物品 $i$ 的一部分，那么如何选择装入背包中的物品，使得装入背包中的物品总价值最大？

算法思想#

首先计算每种物品单位重量的价值 $\frac {v_i} {w_i}$ ，然后依据贪心策略，将尽可能多的单位价值最高的物品装入背包。若装入后总重量未超过背包容量 $c$ ，则继续装入单位重量次高的物品，以此类推，直到背包装满为止。

{% note warning modern %} 与 01 背包区分，背包问题（分数背包问题）由于可以装入物品的一部分，因此是可以全部装满的。 {% endnote %}

代码实现#

1
struct Item {
2
    int weight;
3
    int value;
4
    char *name;  // 物品名称
5
};
6

7
/**
8
 * 贪心算法解决背包问题
9
 *
10
 * @param capacity 背包的容量
11
 * @param items 物品数组
12
 * @param numItems 物品的数量
13
 */
14
void knapsackGreedy(int capacity, struct Item items[], int numItems) {
15
    qsort(items, numItems, sizeof(struct Item), compare);  // 按照单位价值从大到小排序
16

17
    double totalValue = 0.0;  // 背包中物品的总价值
18
    int currentWeight = 0;  // 背包中物品的总重量
19
    int i;
20

21
    for (i = 0; i < numItems; i++) {
22
        if (currentWeight + items[i].weight <= capacity) {  // 物品可以全部装入背包
23
            totalValue += items[i].value;
24
            currentWeight += items[i].weight;
25
            printf("selected all: %s, weight: %d, value: %d\n", items[i].name, items[i].weight, items[i].value);
26
        } else {  // 物品只能部分装入背包
27
            int remain = capacity - currentWeight;
28
            totalValue += items[i].value * ((double)remain / items[i].weight);
29
            printf("selected part: %s, weight: %d, value: %.2f\n", items[i].name, remain, items[i].value * ((double)remain / items[i].weight));
30
            break;  // 背包已经装满，退出循环
31
        }
32
    }
33

34
    printf("max value is: %f\n", totalValue);
35
}

日勿の部落格

基本思想#

活动安排问题#

问题定义#

算法思想#

代码实现#

全局最优解证明#

背包问题#

问题定义#

算法思想#

代码实现#

目录