贪心算法的实践与应用

# 1. 贪心算法概述

## 1.1 贪心算法的定义与特点

贪心算法是一种在每一步选择中都采取当前状态下的最优解，从而希望最终能够达到全局最优解的算法思想。贪心算法具有以下特点：
- 简单：贪心算法的实现相对简单，通常只需要考虑局部最优解的选择。
- 高效：由于贪心算法每一步都选择当前的最优解，因此可以在较短的时间内得到一个相对较好的解。

## 1.2 贪心选择性质及最优子结构

贪心算法的核心是贪心选择性质和最优子结构。贪心选择性质指的是每一步都采取局部最优解的选择，期望通过局部最优解达到全局最优解；最优子结构指的是问题的最优解包含子问题的最优解，可以通过局部最优解推导全局最优解。

## 1.3 贪心算法与动态规划的区别

贪心算法与动态规划常被混淆，它们之间的区别主要在于贪心算法对每个子问题的解决方案都做出选择，不能回退；而动态规划会保存以前的运算结果，并根据以前的结果对当前问题进行选择，有回退功能。

接下来将介绍贪心算法在实践中的具体应用，以展示贪心算法的实际价值。

# 2. 经典贪心算法实践

在这一章中，我们将介绍几个经典的贪心算法问题，并给出相应的实现代码。贪心算法通常在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解。

### 2.1 零钱找零问题

在零钱找零问题中，我们需要找零n美分，假设可用的硬币面额为1美分、5美分、10美分、25美分，求最少需要的硬币数量。

#### Python实现：

def min_coins(coins, n):
    coins.sort(reverse=True)
    num_coins = 0
    i = 0
    while n > 0:
        if coins[i] <= n:
            num_coins += n // coins[i]
            n %= coins[i]
        i += 1
    return num_coins

coins = [1, 5, 10, 25]
n = 47
print(f"最少需要的硬币数量为：{min_coins(coins, n)}")

#### 代码总结：
在零钱找零问题中，我们按照硬币面额从大到小的顺序贪心地选择硬币，直到找零数为0为止。

#### 结果说明：
对于找零数为47美分的情况，最少需要的硬币数量为5个。

### 2.2 活动选择问题

活动选择问题是计划多个活动在同一时间段举行，每个活动都有一个起始时间和结束时间，问如何安排活动使得参与的活动数量最大。

#### Java实现：

import java.util.*;

class Activity {
    int start;
    int end;

    public Activity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class ActivitySelection {
    public static int maxActivities(Activity[] activities) {
        Arrays.sort(activities, (a, b) -> a.end - b.end);
        int count = 1;
        int prevEnd = activities[0].end;

        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= prevEnd) {
                count++;
                prevEnd = activities[i].end;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Activity[] activities = {new Activity(1, 4), new Activity(3, 5), new Activity(0, 6), new Activity(5, 7), new Activity(3, 8), new Activity(5, 9), new Activity(6, 10), new Activity(8, 11), new Activity(8, 12), new Activity(2, 13), new Activity(12, 14)};
        System.out.println("最多可安排的活动数量为：" + maxActivities(activities));
    }
}

#### 代码总结：
活动选择问题中，我们按照活动结束时间从小到大排序，贪心地选择结束时间最早并且与之前活动不重叠的活动。

#### 结果说明：
在给定的活动安排下，最多可安排的活动数量为4。

### 2.3 区间调度问题

区间调度问题是给定n个闭区间，选择尽量多的互不重叠的区间。

#### Go实现：

package main

import (
	"fmt"
	"sort"
)

type Interval struct {
	Start int
	End   int
}

func maxNonOverlapping(intervals []Interval) int {
	if len(intervals) == 0 {
		return 0
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i].End < intervals[j].End
	})

	count := 1
	end := intervals[0].End

	for i := 1; i < len(intervals); i++ {
		if intervals[i].Start >= end {
			count++
			end = intervals[i].End
		}
	}
	return count
}

func main() {
	intervals := []Interval{{1, 3}, {2, 4}, {3, 6}, {5, 7}, {6, 8}, {7, 9}}
	fmt.Println("最多可安排的互不重叠区间数量为:", maxNonOverlapping(intervals))
}

#### 代码总结：
区间调度问题中，我们按照区间的结束位置从小到大排序，贪心地选择结束位置最早并且与之前区间不重叠的区间。

#### 结果说明：
在给定的区间集合下，最多可