贪心算法：局部最优的全局策略

算法原理

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优选择的算法策略，希望通过一系列局部最优选择导致全局最优解。贪心算法不会回溯，一旦做出选择就不再改变。

基本思想

1. 建立模型：将求解过程看作一系列选择
2. 贪心选择：每步选择当前看起来最优的选项
3. 局部最优：不考虑全局，只关注当前最好的选择
4. 不可回溯：一旦选择就不再更改
5. 期望全局最优：希望局部最优能导致全局最优

适用条件

1. 贪心选择性质：局部最优选择可以导致全局最优解
2. 最优子结构：问题的最优解包含子问题的最优解

优缺点分析

优点

1. 实现简单：算法逻辑直观，编码容易
2. 效率高：通常具有较低的时间复杂度
3. 空间节省：不需要存储中间状态
4. 实时性好：可以在线处理数据

缺点

1. 不保证最优：很多问题无法得到全局最优解
2. 适用范围有限：只适用于特定类型的问题
3. 难以验证：需要数学证明贪心策略的正确性
4. 缺乏灵活性：无法处理复杂的约束条件

使用场景

适用场景

1. 调度问题：任务调度、会议安排
2. 图论问题：最小生成树、最短路径
3. 编码问题：哈夫曼编码
4. 资源分配：背包问题的某些变种
5. 几何问题：区间覆盖、点覆盖

C语言实现

经典贪心算法实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>

#define MAX_N 1000

/**
 * 1. 活动选择问题（区间调度）
 */
typedef struct Activity {
    int start;
    int finish;
    int id;
} Activity;

int compare_activities(const void* a, const void* b) {
    Activity* act1 = (Activity*)a;
    Activity* act2 = (Activity*)b;
    return act1->finish - act2->finish; // 按结束时间升序排序
}

int activity_selection(Activity activities[], int n) {
    // 按结束时间排序
    qsort(activities, n, sizeof(Activity), compare_activities);
    
    printf("选择的活动:\n");
    printf("活动%d: [%d, %d]\n", activities[0].id, 
           activities[0].start, activities[0].finish);
    
    int count = 1;
    int last_finish = activities[0].finish;
    
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= last_finish) {
            printf("活动%d: [%d, %d]\n", activities[i].id,
                   activities[i].start, activities[i].finish);
            last_finish = activities[i].finish;
            count++;
        }
    }
    
    return count;
}

/**
 * 2. 分数背包问题
 */
typedef struct Item {
    int weight;
    int value;
    double ratio; // 价值密度
    int id;
} Item;

int compare_items(const void* a, const void* b) {
    Item* item1 = (Item*)a;
    Item* item2 = (Item*)b;
    if (item2->ratio > item1->ratio) return 1;
    if (item2->ratio < item1->ratio) return -1;
    return 0;
}

double fractional_knapsack(Item items[], int n, int capacity) {
    // 计算价值密度并排序
    for (int i = 0; i < n; i++) {
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
    
    qsort(items, n, sizeof(Item), compare_items);
    
    double total_value = 0.0;
    int remaining_capacity = capacity;
    
    printf("贪心选择过程:\n");
    
    for (int i = 0; i < n; i++) {
        if (remaining_capacity >= items[i].weight) {
            // 完全装入
            total_value += items[i].value;
            remaining_capacity -= items[i].weight;
            printf("物品%d: 完全装入，重量%d，价值%d\n", 
                   items[i].id, items[i].weight, items[i].value);
        } else if (remaining_capacity > 0) {
            // 部分装入
            double fraction = (double)remaining_capacity / items[i].weight;
            total_value += items[i].value * fraction;
            printf("物品%d: 装入%.2f，重量%d，价值%.2f\n", 
                   items[i].id, fraction, remaining_capacity, 
                   items[i].value * fraction);
            remaining_capacity = 0;
            break;
        }
    }
    
    return total_value;
}

/**
 * 3. 哈夫曼编码
 */
typedef struct HuffmanNode {
    char character;
    int frequency;
    struct HuffmanNode* left;
    struct HuffmanNode* right;
} HuffmanNode;

typedef struct MinHeap {
    int size;
    int capacity;
    HuffmanNode** array;
} MinHeap;

HuffmanNode* create_node(char character, int frequency) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->character = character;
    node->frequency = frequency;
    node->left = node->right = NULL;
    return node;
}

MinHeap* create_min_heap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->array = (HuffmanNode**)malloc(capacity * sizeof(HuffmanNode*));
    return heap;
}

void swap_nodes(HuffmanNode** a, HuffmanNode** b) {
    HuffmanNode* temp = *a;
    *a = *b;
    *b = temp;
}

void min_heapify(MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < heap->size && 
        heap->array[left]->frequency < heap->array[smallest]->frequency) {
        smallest = left;
    }
    
    if (right < heap->size && 
        heap->array[right]->frequency < heap->array[smallest]->frequency) {
        smallest = right;
    }
    
    if (smallest != idx) {
        swap_nodes(&heap->array[smallest], &heap->array[idx]);
        min_heapify(heap, smallest);
    }
}

HuffmanNode* extract_min(MinHeap* heap) {
    HuffmanNode* temp = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    min_heapify(heap, 0);
    return temp;
}

void insert_min_heap(MinHeap* heap, HuffmanNode* node) {
    heap->size++;
    int i = heap->size - 1;
    
    while (i && node->frequency < heap->array[(i - 1) / 2]->frequency) {
        heap->array[i] = heap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    
    heap->array[i] = node;
}

void print_huffman_codes(HuffmanNode* root, char* code, int top) {
    if (root->left) {
        code[top] = '0';
        print_huffman_codes(root->left, code, top + 1);
    }
    
    if (root->right) {
        code[top] = '1';
        print_huffman_codes(root->right, code, top + 1);
    }
    
    if (!root->left && !root->right) {
        printf("字符 '%c': ", root->character);
        for (int i = 0; i < top; i++) {
            printf("%c", code[i]);
        }
        printf("\n");
    }
}

HuffmanNode* build_huffman_tree(char characters[], int frequencies[], int n) {
    MinHeap* heap = create_min_heap(n);
    
    // 创建叶子节点并插入堆
    for (int i = 0; i < n; i++) {
        HuffmanNode* node = create_node(characters[i], frequencies[i]);
        insert_min_heap(heap, node);
    }
    
    // 构建哈夫曼树
    while (heap->size > 1) {
        HuffmanNode* left = extract_min(heap);
        HuffmanNode* right = extract_min(heap);
        
        HuffmanNode* merged = create_node('$', left->frequency + right->frequency);
        merged->left = left;
        merged->right = right;
        
        insert_min_heap(heap, merged);
    }
    
    return extract_min(heap);
}

/**
 * 4. 最小生成树 - Kruskal算法
 */
typedef struct Edge {
    int src, dest, weight;
} Edge;

typedef struct Graph {
    int vertices, edges;
    Edge* edge_list;
} Graph;

Graph* create_graph(int vertices, int edges) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;
    graph->edges = edges;
    graph->edge_list = (Edge*)malloc(edges * sizeof(Edge));
    return graph;
}

int compare_edges(const void* a, const void* b) {
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;
    return edge1->weight - edge2->weight;
}

// 并查集操作
int find_parent(int parent[], int i) {
    if (parent[i] == i) return i;
    return parent[i] = find_parent(parent, parent[i]); // 路径压缩
}

void union_sets(int parent[], int rank[], int x, int y) {
    int root_x = find_parent(parent, x);
    int root_y = find_parent(parent, y);
    
    if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y;
    } else if (rank[root_x] > rank[root_y]) {
        parent[root_y] = root_x;
    } else {
        parent[root_y] = root_x;
        rank[root_x]++;
    }
}

void kruskal_mst(Graph* graph) {
    int vertices = graph->vertices;
    Edge result[vertices - 1];
    int result_index = 0;
    
    // 按权重排序
    qsort(graph->edge_list, graph->edges, sizeof(Edge), compare_edges);
    
    // 初始化并查集
    int* parent = (int*)malloc(vertices * sizeof(int));
    int* rank = (int*)calloc(vertices, sizeof(int));
    
    for (int v = 0; v < vertices; v++) {
        parent[v] = v;
    }
    
    printf("Kruskal最小生成树的边:\n");
    int total_weight = 0;
    
    for (int i = 0; i < graph->edges && result_index < vertices - 1; i++) {
        Edge current_edge = graph->edge_list[i];
        
        int x = find_parent(parent, current_edge.src);
        int y = find_parent(parent, current_edge.dest);
        
        if (x != y) {
            result[result_index++] = current_edge;
            union_sets(parent, rank, x, y);
            printf("边 %d-%d: 权重 %d\n", 
                   current_edge.src, current_edge.dest, current_edge.weight);
            total_weight += current_edge.weight;
        }
    }
    
    printf("最小生成树总权重: %d\n", total_weight);
    
    free(parent);
    free(rank);
}

/**
 * 5. 硬币找零（贪心版本）
 */
void coin_change_greedy(int coins[], int n, int amount) {
    printf("找零 %d 元的硬币组合:\n", amount);
    
    // 假设硬币已按面值降序排列
    for (int i = 0; i < n; i++) {
        int count = amount / coins[i];
        if (count > 0) {
            printf("%d元硬币: %d个\n", coins[i], count);
            amount %= coins[i];
        }
    }
    
    if (amount > 0) {
        printf("无法完全找零，剩余: %d元\n", amount);
    }
}

/**
 * 6. 会议室安排问题
 */
typedef struct Meeting {
    int start;
    int end;
    int id;
} Meeting;

int compare_meetings(const void* a, const void* b) {
    Meeting* m1 = (Meeting*)a;
    Meeting* m2 = (Meeting*)b;
    return m1->end - m2->end;
}

int schedule_meetings(Meeting meetings[], int n) {
    qsort(meetings, n, sizeof(Meeting), compare_meetings);
    
    printf("安排的会议:\n");
    printf("会议%d: [%d, %d]\n", meetings[0].id, meetings[0].start, meetings[0].end);
    
    int count = 1;
    int last_end = meetings[0].end;
    
    for (int i = 1; i < n; i++) {
        if (meetings[i].start >= last_end) {
            printf("会议%d: [%d, %d]\n", meetings[i].id, 
                   meetings[i].start, meetings[i].end);
            last_end = meetings[i].end;
            count++;
        }
    }
    
    return count;
}

/**
 * 7. 跳跃游戏
 */
bool can_jump(int nums[], int n) {
    int max_reach = 0;
    
    for (int i = 0; i < n; i++) {
        if (i > max_reach) {
            return false; // 无法到达当前位置
        }
        
        max_reach = max_reach > (i + nums[i]) ? max_reach : (i + nums[i]);
        
        if (max_reach >= n - 1) {
            return true; // 可以到达最后一个位置
        }
    }
    
    return max_reach >= n - 1;
}

int min_jumps(int nums[], int n) {
    if (n <= 1) return 0;
    
    int jumps = 0;
    int current_end = 0;
    int farthest = 0;
    
    for (int i = 0; i < n - 1; i++) {
        farthest = farthest > (i + nums[i]) ? farthest : (i + nums[i]);
        
        if (i == current_end) {
            jumps++;
            current_end = farthest;
        }
    }
    
    return jumps;
}

// 测试函数
void test_activity_selection() {
    printf("=== 活动选择问题测试 ===\n");
    
    Activity activities[] = {
        {1, 4, 1}, {3, 5, 2}, {0, 6, 3}, {5, 7, 4}, 
        {8, 9, 5}, {5, 9, 6}, {6, 10, 7}, {8, 11, 8}, 
        {2, 13, 9}, {12, 14, 10}
    };
    int n = sizeof(activities) / sizeof(activities[0]);
    
    int max_activities = activity_selection(activities, n);
    printf("最多可以安排 %d 个活动\n\n", max_activities);
}

void test_fractional_knapsack() {
    printf("=== 分数背包问题测试 ===\n");
    
    Item items[] = {
        {20, 100, 0, 1}, {30, 120, 0, 2}, {10, 60, 0, 3}
    };
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 50;
    
    printf("背包容量: %d\n", capacity);
    double max_value = fractional_knapsack(items, n, capacity);
    printf("最大价值: %.2f\n\n", max_value);
}

void test_huffman_coding() {
    printf("=== 哈夫曼编码测试 ===\n");
    
    char characters[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int frequencies[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(characters) / sizeof(characters[0]);
    
    HuffmanNode* root = build_huffman_tree(characters, frequencies, n);
    
    char code[MAX_N];
    printf("哈夫曼编码:\n");
    print_huffman_codes(root, code, 0);
    printf("\n");
}

void test_kruskal() {
    printf("=== Kruskal最小生成树测试 ===\n");
    
    Graph* graph = create_graph(4, 5);
    
    // 添加边
    graph->edge_list[0] = (Edge){0, 1, 10};
    graph->edge_list[1] = (Edge){0, 2, 6};
    graph->edge_list[2] = (Edge){0, 3, 5};
    graph->edge_list[3] = (Edge){1, 3, 15};
    graph->edge_list[4] = (Edge){2, 3, 4};
    
    kruskal_mst(graph);
    printf("\n");
}

void test_coin_change() {
    printf("=== 硬币找零测试 ===\n");
    
    int coins[] = {25, 10, 5, 1}; // 降序排列
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 67;
    
    coin_change_greedy(coins, n, amount);
    printf("\n");
}

void test_jump_game() {
    printf("=== 跳跃游戏测试 ===\n");
    
    int nums1[] = {2, 3, 1, 1, 4};
    int n1 = sizeof(nums1) / sizeof(nums1[0]);
    
    printf("数组: ");
    for (int i = 0; i < n1; i++) printf("%d ", nums1[i]);
    printf("\n");
    
    printf("能否到达终点: %s\n", can_jump(nums1, n1) ? "是" : "否");
    printf("最少跳跃次数: %d\n", min_jumps(nums1, n1));
    printf("\n");
}

int main() {
    test_activity_selection();
    test_fractional_knapsack();
    test_huffman_coding();
    test_kruskal();
    test_coin_change();
    test_jump_game();
    
    return 0;
}

贪心策略设计原则

1. 贪心选择的正确性

要证明贪心算法的正确性，通常需要证明：

• 贪心选择性质：局部最优选择可以导致全局最优
• 最优子结构：问题的最优解包含子问题的最优解

2. 常见的贪心策略

1. 按截止时间排序：任务调度问题
2. 按价值密度排序：背包问题
3. 按权重排序：最小生成树
4. 按频率排序：哈夫曼编码

复杂度分析

时间复杂度

通常由排序步骤决定：

• 排序主导：O(n log n)
• 线性扫描：O(n)
• 总体复杂度：通常为O(n log n)

空间复杂度

• 基本贪心：O(1)
• 需要排序：O(n)

实际应用

1. 操作系统：进程调度、内存分配
2. 网络协议：路由选择、流量控制
3. 编译器：寄存器分配、代码优化
4. 数据压缩：哈夫曼编码、LZ算法
5. 图论算法：最短路径、最小生成树

总结

贪心算法是一类重要的算法设计策略，虽然不能保证在所有问题上都能得到最优解，但在许多实际问题中表现优秀。其简单、高效的特点使得它在实时系统和在线算法中有广泛应用。掌握贪心算法的关键在于理解何时可以应用贪心策略，以及如何设计正确的贪心选择准则。

版权所有，如有侵权请联系我