Given list of N items where each item has some [weight, value] associated with it, put the items into a knapsack of capacity W to maximize the sum of values associated with the items Break items for maximizing total value is allowed.

Hint

Calculate the "value per unit weight" for each item. This tells you how much value you get for each unit of weight you carry. Sort this items. Start with the item that gives you the highest value per unit weight. If you have enough space in your knapsack, take the whole item. Move on to the next most valuable item and repeat. If you don't have enough space for the whole item, take as much of it as you can fit.

# Python implementation

list = [[120, 30], [60, 10], [100, 20]]
W = 50

list.sort(key = lambda x: x[0]/x[1], reverse = True)
output = 0

for i in range(len(list)):
  if list[i][1] < W:
    W -= list[i][1]
    output += list[i][0]
  else:
    output += list[i][0] * W / list[i][1]
    W = 0

print(output)

// Javascript implementation

const list = [[120, 30], [60, 10], [100, 20]];
let W = 50;

list.sort((a, b) => (b[0]/b[1]) - (a[0]/a[1]));
let output = 0;

for (let i = 0; i < list.length; i++) {
  if (list[i][1] < W) {
    W -= list[i][1]
    output += list[i][0];
  } else {
    output += list[i][0] * W / list[i][1];
    W = 0;
  }
}

console.log(output);

Fractional Knapsack

Hint