js 实现贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。请注意，贪心算法并不总是能保证得到全局最优解，但在某些问题上，它可以提供足够好的解决方案。下面是一个使用JavaScript实现的贪心算法示例，解决“ fractional knapsack problem”（分数背包问题）。

分数背包问题描述：有N件物品和一个容量为W的背包，每种物品有一个价值（value）和重量（weight），要求在不超过背包总重量的前提下，让背包中装入的物品总价值最大。

function fractionalKnapsack(values, weights, capacity) {
    // 创建一个数组，每个元素是一个对象，包含物品的价值、重量和单位价值（价值/重量）
    let items = values.map((value, index) => ({value, weight: weights[index], ratio: value / weights[index]}));
    
    // 按单位价值降序排序物品
    items.sort((a, b) => b.ratio - a.ratio);
    
    let totalValue = 0; // 背包中物品的总价值
    
    for (let item of items) {
        if (capacity >= item.weight) {
            // 完全装入当前物品
            capacity -= item.weight;
            totalValue += item.value;
        } else {
            // 只能部分装入当前物品
            totalValue += (capacity * item.ratio);
            break; // 背包已满，停止循环
        }
    }
    
    return totalValue;
}

// 示例
let values = [60, 100, 120]; // 物品的价值
let weights = [10, 20, 30];  // 物品的重量
let capacity = 50;           // 背包的容量
console.log(fractionalKnapsack(values, weights, capacity)); // 输出最大价值

这段代码首先计算每件物品的单位价值（即价值与重量的比值），然后按单位价值降序排序。接下来，从价值密度最高的物品开始尝试放入背包，如果物品可以完全放入，则直接计算价值；如果不能完全放入，则根据剩余容量按比例计算该物品能贡献的价值。这种方法就是典型的贪心策略，每次选择局部最优（即单位价值最高）的物品处理，最终达到全局较优的解。