Advertisement
Guest User

Untitled

a guest
Sep 26th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.67 KB | None | 0 0
  1. function comp(firstItem, secondItem) {
  2. const firstCoeff = firstItem['value'] / firstItem['weight'];
  3. const secondCoeff = secondItem['value'] / secondItem['weight'];
  4. return secondCoeff - firstCoeff;
  5. }
  6.  
  7. function knapsack(w, items) {
  8. let result = [];
  9.  
  10. items = items.sort(comp);
  11. for (let i = 0, length = items.length; i < length; i++) {
  12. if (w >= items[i]['weight']) {
  13. result.push(items[i]);
  14. w -= items[i]['weight'];
  15. } else {
  16. break;
  17. }
  18. }
  19.  
  20. return result;
  21. }
  22.  
  23. const w = 80;
  24. const items = [
  25. {'weight': 15, 'value': 60},
  26. {'weight': 50, 'value': 100},
  27. {'weight': 30, 'value': 90}
  28. ];
  29.  
  30. const result = knapsack(w, items);
  31. console.log(result);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement