贪心算法

📘 第八部分：贪心算法

第20讲：贪心算法 ⭐⭐

🔑 知识点讲解

贪心策略：每一步都选择当前最优解，希望最终得到全局最优解。

适用条件：
1. 贪心选择性质：局部最优能导致全局最优
2. 最优子结构：问题的最优解包含子问题的最优解

经典贪心问题：
1. 活动选择（区间调度）
2. 分数背包
3. 哈夫曼编码
4. Dijkstra最短路径
5. Prim/Kruskal最小生成树
6. 找零钱问题

⚠️ 贪心不一定能得到最优解。
    0-1背包问题，贪心不行，需要动态规划。

✏️ 练习14：活动选择问题

题目：有 n 个活动，每个活动有开始时间和结束时间。同一时间只能参加一个活动，求最多能参加多少个活动。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start, end;
} Activity;

int cmp(const void *a, const void *b) {
    return ((Activity *)a)->end - ((Activity *)b)->end;
}

int main() {
    int n;
    scanf("%d", &n);
    
    Activity act[100];
    for (int i = 0; i < n; i++)
        scanf("%d %d", &act[i].start, &act[i].end);
    
    // 贪心：按结束时间排序
    qsort(act, n, sizeof(Activity), cmp);
    
    int count = 1;
    int lastEnd = act[0].end;
    
    printf("选择活动: [%d,%d]", act[0].start, act[0].end);
    
    for (int i = 1; i < n; i++) {
        if (act[i].start >= lastEnd) {
            count++;
            lastEnd = act[i].end;
            printf(" [%d,%d]", act[i].start, act[i].end);
        }
    }
    
    printf("\n最多参加 %d 个活动\n", count);
    return 0;
}

✏️ 练习15：分数背包问题

题目：有 n 个物品，每个有重量和价值。背包容量为 W，物品可以分割。求最大价值。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double weight, value;
    double ratio;  // 性价比
} Item;

int cmp(const void *a, const void *b) {
    double diff = ((Item *)b)->ratio - ((Item *)a)->ratio;
    return diff > 0 ? 1 : (diff < 0 ? -1 : 0);
}

int main() {
    int n;
    double W;
    scanf("%d %lf", &n, &W);
    
    Item items[100];
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &items[i].weight, &items[i].value);
        items[i].ratio = items[i].value / items[i].weight;
    }
    
    // 按性价比降序排序
    qsort(items, n, sizeof(Item), cmp);
    
    double totalValue = 0;
    double remain = W;
    
    for (int i = 0; i < n && remain > 0; i++) {
        if (items[i].weight <= remain) {
            // 整个物品装入
            totalValue += items[i].value;
            remain -= items[i].weight;
        } else {
            // 装入部分
            totalValue += remain * items[i].ratio;
            remain = 0;
        }
    }
    
    printf("最大价值: %.2f\n", totalValue);
    return 0;
}