JS基于贪心算法解决背包问题示例

JS基于贪心算法解决背包问题示例

什么是贪心算法

贪心算法是一种直接寻求局部最优解以达到全局最优的算法，即采取贪心策略，每次做出当时看来最好的选择，不考虑将来的结果，也不进行回溯，只关心眼前的选择会不会对当前局面产生最优的影响。贪心算法的特点是简单、高效、易于证明正确性，并且常用于求解组合优化问题，如背包问题、最小生成树问题、哈夫曼编码等。

背包问题

背包问题是组合优化中的一个经典问题，其描述为：给定一个可装载重量为W的背包和n个物品，第i个物品的重量为wi，价值为vi，要求选出若干个物品放入背包中，使得装入背包的物品总重量不超过W，且总价值最大。

贪心算法解决背包问题

贪心算法求解背包问题的基本思路是按单位重量价值从高到低排序，优先选择单位重量价值高的物品，直到重量超过背包容量或者物品全部选择完毕。

function knapSack(capacity, weights, values) {
  var n = values.length; // 物品数量
  var load = 0; // 已装载的物品重量
  var val = 0; // 已装载的物品价值

  // 按单位重量价值从高到低排序
  var valPerWt = [];
  for (var i = 0; i < n; i++) {
    valPerWt[i] = values[i] / weights[i];
  }
  valPerWt.sort(function(a, b) {
    return b - a;
  });

  // 依次选择单位重量价值高的物品，直到重量超过背包容量或者物品全部选择完毕
  for (var i = 0; i < n; i++) {
    var j = valPerWt.indexOf(values[i] / weights[i]);
    if (weights[j] <= (capacity - load)) {
      load += weights[j];
      val += values[j];
      valPerWt.splice(j, 1);
      weights.splice(j, 1);
      values.splice(j, 1);
      i--;
    } else {
      var k = Math.floor((capacity - load) / weights[j]);
      load += k * weights[j];
      val += k * values[j];
      break;
    }
  }

  return val;
}

示例一

假设背包容量为10，有如下5个物品：

物品编号	重量	价值
1	2	11
2	3	7
3	4	15
4	5	6
5	6	18

运行下面的代码：

var capacity = 10;
var weights = [2, 3, 4, 5, 6];
var values = [11, 7, 15, 6, 18];
console.log(knapSack(capacity, weights, values));

输出结果为：34，表示选取物品3和物品5，总重量为10，总价值为34。

示例二

假设背包容量为20，有如下6个物品：

物品编号	重量	价值
1	5	10
2	10	19
3	15	30
4	20	40
5	25	50
6	30	60

运行下面的代码：

var capacity = 20;
var weights = [5, 10, 15, 20, 25, 30];
var values = [10, 19, 30, 40, 50, 60];
console.log(knapSack(capacity, weights, values));

输出结果为：149，表示选取物品1、物品2、物品3和物品6，总重量为20，总价值为149。