贪心算法中背包问题代码

以下是Python和JS两种语言基于贪心算法解决背包问题的代码：

Python代码：

def fractional_knapsack(value, weight, capacity):
    """Return maximum value of items and their fractional amounts.
 
    (max_value, fractions) is returned where max_value is the maximum value of
    items with total weight not more than capacity.
    fractions is a list where fractions[i] is the fraction that should be taken
    of item i, where 0 <= i < total number of items.
 
    value[i] is the value of item i and weight[i] is the weight of item i
    for 0 <= i < n where n is the number of items.
 
    capacity is the maximum weight.
    """
    index = list(range(len(value)))
    # contains ratios of values to weight
    ratio = [v/w for v, w in zip(value, weight)]
    # index is sorted according to value-to-weight ratio in decreasing order
    index.sort(key=lambda i: ratio[i], reverse=True)
 
    max_value = 0
    fractions = [0]*len(value)
    for i in index:
        if weight[i] <= capacity:
            fractions[i] = 1
            max_value += value[i]
            capacity -= weight[i]
        else:
            fractions[i] = capacity/weight[i]
            max_value += value[i]*capacity/weight[i]
            break
 
    return max_value, fractions

JS代码：

function knapsack(capacity, weights, values) {
  var n = values.length;
  var load = 0;
  var i = 0;
  var val = 0;
  while (load < capacity && i < n) {
    if (weights[i] <= (capacity - load)) {
      val += values[i];
      load += weights[i];
    } else {
      var r = (capacity - load) / weights[i];
      val += r * values[i];
      load += weights[i];
    }
    i++;
  }
  return val;
}