贪心算法（Greedy Algorithm）

leetcode
● 455.分发饼干
● 122.买卖股票的最佳时机 II

贪心算法（Greedy Algorithm）的认识

贪心算法是一种在每一步选择中都采取当前状态下最优（或最有利）的选择，从而希望导致结果是全局最优的算法策略。

贪心算法不是对所有问题都能得到全局最优解，但对一类问题（具有贪心选择性质的问题）可以。

结果并不一定是最优的,常见的反面例子如：零钱兑换问题。

贪心算法的特点

1. 局部最优选择：每一步都做出当前看起来最好的选择
2. 不可回溯：一旦做出选择，不再更改
3. 高效性：通常时间复杂度较低
4. 简单性：算法逻辑相对简单直观

贪心算法的适用条件

1. 贪心选择性质：全局最优解包含局部最优解
2. 最优子结构：问题的最优解包含子问题的最优解
3. 问题具有贪心选择性质：通过局部最优选择可以达到全局最优

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

贪心算法的原理

贪心算法的基本原理可以概括为以下步骤：

1. 问题分析：确定问题是否适合贪心算法
2. 贪心策略选择：确定每一步的贪心选择标准
3. 局部最优选择：在每一步做出当前最优选择
4. 构建解：通过一系列局部最优选择构建全局解
5. 验证正确性：验证算法是否能得到全局最优解

JavaScript中的贪心算法应用

1. 活动选择问题

// 活动选择问题：选择最多不重叠的活动
function activitySelection(startTimes, endTimes) {
    // 将活动按结束时间排序
    const activities = startTimes.map((start, i) => ({
        start: start,
        end: endTimes[i]
    })).sort((a, b) => a.end - b.end);
    
    const selected = [activities[0]]; // 选择第一个结束的活动
    let lastEnd = activities[0].end;
    
    // 贪心选择：每次选择结束最早且不冲突的活动
    for (let i = 1; i < activities.length; i++) {
        if (activities[i].start >= lastEnd) {
            selected.push(activities[i]);
            lastEnd = activities[i].end;
        }
    }
    
    return selected;
}

// 使用示例
const startTimes = [1, 3, 0, 5, 8, 5];
const endTimes = [2, 4, 6, 7, 9, 9];
console.log(activitySelection(startTimes, endTimes));
// 输出: [{start:1,end:2}, {start:3,end:4}, {start:5,end:7}, {start:8,end:9}]

2. 分数背包问题

// 分数背包问题：选择物品以最大化总价值
function fractionalKnapsack(capacity, weights, values) {
    const n = weights.length;
    const items = [];
    
    // 计算每个物品的单位价值
    for (let i = 0; i < n; i++) {
        items.push({
            weight: weights[i],
            value: values[i],
            ratio: values[i] / weights[i]
        });
    }
    
    // 按单位价值降序排序
    items.sort((a, b) => b.ratio - a.ratio);
    
    let totalValue = 0;
    let remainingCapacity = capacity;
    const selectedItems = [];
    
    // 贪心选择：优先选择单位价值最高的物品
    for (const item of items) {
        if (remainingCapacity >= item.weight) {
            // 可以完整放入
            selectedItems.push({
                item: item,
                fraction: 1
            });
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // 部分放入
            selectedItems.push({
                item: item,
                fraction: remainingCapacity / item.weight
            });
            totalValue += item.value * (remainingCapacity / item.weight);
            break;
        }
    }
    
    return {
        totalValue: totalValue,
        selectedItems: selectedItems
    };
}

// 使用示例
const capacity = 50;
const weights = [10, 20, 30];
const values = [60, 100, 120];
console.log(fractionalKnapsack(capacity, weights, values));
// 输出: {totalValue: 240, selectedItems: [...]}

3. 最小生成树（Kruskal算法）

// 最小生成树：Kruskal算法
class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size }, (_, i) => i);
    }
    
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
            return true;
        }
        return false;
    }
}

function kruskalMST(vertices, edges) {
    // 按权重排序边
    edges.sort((a, b) => a.weight - b.weight);
    
    const uf = new UnionFind(vertices.length);
    const mst = [];
    let totalWeight = 0;
    
    // 贪心选择：每次选择权重最小的边
    for (const edge of edges) {
        if (uf.union(edge.u, edge.v)) {
            mst.push(edge);
            totalWeight += edge.weight;
            if (mst.length === vertices.length - 1) break;
        }
    }
    
    return {
        mst: mst,
        totalWeight: totalWeight
    };
}

// 使用示例
const vertices = ['A', 'B', 'C', 'D', 'E'];
const edges = [
    { u: 0, v: 1, weight: 4 },
    { u: 0, v: 2, weight: 1 },
    { u: 1, v: 2, weight: 3 },
    { u: 1, v: 3, weight: 2 },
    { u: 2, v: 3, weight: 5 },
    { u: 3, v: 4, weight: 7 }
];
console.log(kruskalMST(vertices, edges));
// 输出: {mst: [...], totalWeight: 10}

4. Huffman编码

// Huffman编码：构建最优前缀码
class HuffmanNode {
    constructor(char, freq, left = null, right = null) {
        this.char = char;
        this.freq = freq;
        this.left = left;
        this.right = right;
    }
}

class PriorityQueue {
    constructor() {
        this.values = [];
    }
    
    enqueue(node) {
        this.values.push(node);
        this.bubbleUp();
    }
    
    bubbleUp() {
        let index = this.values.length - 1;
        const element = this.values[index];
        
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            let parent = this.values[parentIndex];
            
            if (element.freq >= parent.freq) break;
            
            this.values[index] = parent;
            this.values[parentIndex] = element;
            index = parentIndex;
        }
    }
    
    dequeue() {
        const min = this.values[0];
        const end = this.values.pop();
        
        if (this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        
        return min;
    }
    
    sinkDown() {
        let index = 0;
        const length = this.values.length;
        const element = this.values[0];
        
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;
            
            if (leftChildIndex < length) {
                leftChild = this.values[leftChildIndex];
                if (leftChild.freq < element.freq) {
                    swap = leftChildIndex;
                }
            }
            
            if (rightChildIndex < length) {
                rightChild = this.values[rightChildIndex];
                if (
                    (swap === null && rightChild.freq < element.freq) ||
                    (swap !== null && rightChild.freq < leftChild.freq)
                ) {
                    swap = rightChildIndex;
                }
            }
            
            if (swap === null) break;
            
            this.values[index] = this.values[swap];
            this.values[swap] = element;
            index = swap;
        }
    }
}

function buildHuffmanTree(freqMap) {
    const queue = new PriorityQueue();
    
    // 初始化优先队列
    for (const [char, freq] of Object.entries(freqMap)) {
        queue.enqueue(new HuffmanNode(char, freq));
    }
    
    // 构建Huffman树
    while (queue.values.length > 1) {
        const left = queue.dequeue();
        const right = queue.dequeue();
        const merged = new HuffmanNode(
            null,
            left.freq + right.freq,
            left,
            right
        );
        queue.enqueue(merged);
    }
    
    return queue.dequeue();
}

function generateCodes(root, currentCode = '', codeMap = {}) {
    if (root === null) return;
    
    if (root.char !== null) {
        codeMap[root.char] = currentCode || '0';
        return;
    }
    
    generateCodes(root.left, currentCode + '0', codeMap);
    generateCodes(root.right, currentCode + '1', codeMap);
    
    return codeMap;
}

function huffmanEncoding(text) {
    // 计算频率
    const freqMap = {};
    for (const char of text) {
        freqMap[char] = (freqMap[char] || 0) + 1;
    }
    
    // 构建Huffman树
    const root = buildHuffmanTree(freqMap);
    
    // 生成编码
    const codeMap = generateCodes(root);
    
    // 编码文本
    let encodedText = '';
    for (const char of text) {
        encodedText += codeMap[char];
    }
    
    return {
        encodedText: encodedText,
        codeMap: codeMap,
        freqMap: freqMap
    };
}

// 使用示例
const text = 'hello world';
const result = huffmanEncoding(text);
console.log("编码结果:", result.encodedText);
console.log("编码表:", result.codeMap);

5. 分数到埃及分数

// 将分数分解为埃及分数（单位分数之和）
function egyptianFraction(numerator, denominator) {
    const result = [];
    
    while (numerator !== 0) {
        // 找到最大的单位分数
        let unit = Math.ceil(denominator / numerator);
        result.push(`1/${unit}`);
        
        // 更新分数
        numerator = numerator * unit - denominator;
        denominator = denominator * unit;
        
        // 化简分数
        const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
        const commonDivisor = gcd(numerator, denominator);
        numerator /= commonDivisor;
        denominator /= commonDivisor;
    }
    
    return result;
}

// 使用示例
console.log(egyptianFraction(6, 14));
// 输出: ["1/3", "1/11"]

贪心算法的设计模式

1. 问题分解：将问题分解为一系列子问题
2. 贪心选择：确定每一步的贪心选择标准
3. 可行性检查：确保选择是可行的
4. 最优性验证：验证贪心选择能导致全局最优解

贪心算法的注意事项

1. 适用性验证：不是所有问题都适合贪心算法
2. 正确性证明：需要证明贪心选择性质
3. 边界条件：注意处理边界情况
4. 性能评估：评估时间复杂度和空间复杂度

贪心算法的优缺点

优点：

1. 算法简单直观
2. 通常时间复杂度较低（多为O(n log n)）
3. 空间复杂度通常较低
4. 适合在线算法

缺点：

1. 不一定能得到全局最优解
2. 需要证明贪心选择性质
3. 对问题结构有严格要求
4. 可能需要预处理（如排序）