Knapsack Problem

knapsack-problem.js

function comp(firstItem, secondItem) {
  const firstCoeff = firstItem['value'] / firstItem['weight'];
  const secondCoeff = secondItem['value'] / secondItem['weight'];
  return secondCoeff - firstCoeff;
}

function knapsack(w, items) {
  let result = [];
  
  items = items.sort(comp);
  for (let i = 0, length = items.length; i < length; i++) {
    if (w >= items[i]['weight']) {
      result.push(items[i]);
      w -= items[i]['weight'];
    } else {
      break;
    }
  }
  
  return result;
}

const w = 80;
const items = [
  {'weight': 15, 'value': 60},
  {'weight': 50, 'value': 100},
  {'weight': 30, 'value': 90}
];

const result = knapsack(w, items);
console.log(result);