【JavaScript 算法】贪心算法：局部最优解的构建

空白诗

发布于 2024-07-20 12:39:45

270

发布于 2024-07-20 12:39:45

文章被收录于专栏：【全栈开发之路】

贪心算法（Greedy Algorithm）是一种逐步构建解决方案的方法。在每一步选择中，贪心算法总是选择在当前看来最优的选择，希望通过这些局部最优选择最终能构建出全局最优解。贪心算法的特点是简单高效，但它并不总能保证得到最优解。

一、贪心算法的基本概念

贪心算法的核心思想是每一步都选择当前最优的决策，不考虑未来的影响。贪心算法的基本步骤通常包括以下几个：

选择：选择当前最优的选项。
验证：验证当前选择是否可行（通常包括是否满足约束条件）。
构建：将当前选择加入到最终的解决方案中。

贪心算法的适用场景

贪心算法通常适用于以下场景：

最小生成树：如Kruskal和Prim算法。
最短路径问题：如Dijkstra算法。
区间调度问题：如选择最多的不重叠区间。

二、经典问题及其 JavaScript 实现

1. 零钱兑换问题

假设我们有几种不同面值的硬币，1元、2元和5元。我们希望用最少数量的硬币来凑出某个金额。

问题描述：给定不同面值的硬币和一个总金额，求最少数量的硬币。

/**
 * 求最少数量的硬币组合
 * @param {number[]} coins - 硬币面值数组
 * @param {number} amount - 总金额
 * @returns {number} - 最少硬币数量，如果无法凑出总金额返回 -1
 */
function coinChange(coins, amount) {
    // 硬币面值从大到小排序
    coins.sort((a, b) => b - a);
    let count = 0;

    for (let coin of coins) {
        // 尽量使用当前面值最大的硬币
        let num = Math.floor(amount / coin);
        count += num;
        amount -= num * coin;
        
        // 如果总金额为 0，直接返回
        if (amount === 0) return count;
    }

    // 如果无法凑出总金额，返回 -1
    return -1;
}

// 示例：用1元、2元和5元凑出11元的最少硬币数量
console.log(coinChange([1, 2, 5], 11)); // 输出 3 (5 + 5 + 1)

2. 活动选择问题

假设我们有一组活动，每个活动有开始时间和结束时间。我们希望选择尽可能多的活动，使得它们互不重叠。

问题描述：给定一组活动，选择尽可能多的不重叠活动。

/**
 * 求最多的不重叠活动数量
 * @param {number[][]} activities - 活动的开始和结束时间数组
 * @returns {number} - 最多不重叠活动数量
 */
function maxActivities(activities) {
    // 按照活动结束时间排序
    activities.sort((a, b) => a[1] - b[1]);
    let count = 0;
    let end = 0;

    for (let activity of activities) {
        if (activity[0] >= end) {
            // 选择当前活动
            count++;
            end = activity[1];
        }
    }

    return count;
}

// 示例：选择最多的不重叠活动
console.log(maxActivities([[1, 3], [2, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]));
// 输出 4 (选择活动 [1, 3], [3, 5], [5, 7], [8, 9])

3. 分配问题

假设我们有一组任务和一组工人，每个工人能完成的任务数量有限。我们希望尽可能多地完成任务。

问题描述：给定任务和工人的能力，尽可能多地分配任务。

/**
 * 求最多分配任务数量
 * @param {number[]} tasks - 任务难度数组
 * @param {number[]} workers - 工人能力数组
 * @returns {number} - 最多分配任务数量
 */
function maxTaskAssignment(tasks, workers) {
    // 任务和工人分别排序
    tasks.sort((a, b) => a - b);
    workers.sort((a, b) => a - b);
    let taskIndex = 0;
    let workerIndex = 0;
    let count = 0;

    while (taskIndex < tasks.length && workerIndex < workers.length) {
        if (workers[workerIndex] >= tasks[taskIndex]) {
            // 分配任务给当前工人
            count++;
            taskIndex++;
        }
        workerIndex++;
    }

    return count;
}

// 示例：尽可能多地分配任务
console.log(maxTaskAssignment([1, 2, 3], [3, 2, 1])); // 输出 3 (每个工人完成一个任务)