当前位置：首页 > JavaScript

js实现贪心算法

2026-01-31 02:15:34JavaScript

贪心算法简介

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法。贪心算法常用于解决优化问题，如最短路径、最小生成树等。

贪心算法的基本步骤

贪心算法通常包括以下几个步骤：

建立数学模型来描述问题。
将问题分解为若干个子问题。
对每个子问题求解，得到子问题的局部最优解。
将子问题的局部最优解合成原问题的一个解。

贪心算法的实现示例

以下是几个常见的贪心算法问题的JavaScript实现。

找零钱问题

给定不同面额的硬币和一个总金额，计算可以凑成总金额的最少硬币数。

function coinChange(coins, amount) {
    coins.sort((a, b) => b - a); // 按面额从大到小排序
    let count = 0;
    for (let coin of coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
    }
    return amount === 0 ? count : -1;
}

const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount)); // 输出：3 (5 + 5 + 1)

活动选择问题

给定一组活动，每个活动有开始时间和结束时间，选择尽可能多的互不冲突的活动。

function activitySelection(activities) {
    activities.sort((a, b) => a.end - b.end); // 按结束时间排序
    let selected = [];
    let lastEnd = 0;
    for (let activity of activities) {
        if (activity.start >= lastEnd) {
            selected.push(activity);
            lastEnd = activity.end;
        }
    }
    return selected;
}

const activities = [
    { start: 1, end: 4 },
    { start: 3, end: 5 },
    { start: 0, end: 6 },
    { start: 5, end: 7 },
    { start: 8, end: 9 }
];
console.log(activitySelection(activities));

背包问题（分数背包）

给定物品的重量和价值，选择装入背包的物品，使得总价值最大（物品可以分割）。

function fractionalKnapsack(items, capacity) {
    items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight)); // 按单位价值排序
    let totalValue = 0;
    for (let item of items) {
        if (capacity >= item.weight) {
            capacity -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += (capacity / item.weight) * item.value;
            break;
        }
    }
    return totalValue;
}

const items = [
    { weight: 10, value: 60 },
    { weight: 20, value: 100 },
    { weight: 30, value: 120 }
];
const capacity = 50;
console.log(fractionalKnapsack(items, capacity)); // 输出：240