0/1 Knapsack problem

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 item is not allowed.

Hint

This algorithm recursively explores all possible combinations of items, considering the weight constraint at each step, to find the selection that yields the maximum total profit. At each step, if this chosen item weight exceeds the target weight, we disregard it and proceed with a recursive call on the remaining list. If this chosen item weight is less than the target weight, there are two choices:

• Include the item. Add its profit to the maximum profit that can be obtained from the remaining items with reduced weight capacity (W - weight of the selected item)
• Exclude the item. Calculate the maximum profit that can be obtained from the remaining items with the current weight capacity (W)

Compare the maximum profit achievable in both choices (include or exclude the item). Select the choice that results in the higher profit.

• Python
• Javascript
•  Run

def pick(ls, w):
  if len(ls) <= 0 or w <= 0:
    return 0

  if ls[0][1] > w:
    return pick(ls[1:], w)

  return max(ls[0][0] + pick(ls[1:], w - ls[0][1]), pick(ls[1:], w))

ls = [[120, 3], [60, 1], [100, 2]]
W = 5

print(pick(ls, W))

function pick(list, w) {
  if (list.length <= 0 || w <= 0) {
    return 0;
  }

  if (list[0][1] > w) {
    return pick(list.slice(1), w);
  }

  return Math.max(list[0][0] + pick(list.slice(1), w - list[0][1]), pick(list.slice(1), w));
}

const list = [[120, 3], [60, 1], [100, 2]];
const W = 5;

console.log(pick(list, W));