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 uses memoization to improve performance. It's same as the recursive version of 0/1 Knapsack problem, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

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

  global cache
  if not cache:
    cache = [{} for _ in range(len(ls) + 1)]

  if w not in cache[len(ls)]:
    if ls[0][1] > w:
      cache[len(ls)][w] = pick(ls[1:], w)
    else:
      cache[len(ls)][w] = max(ls[0][0] + pick(ls[1:], w - ls[0][1]), pick(ls[1:], w))

  return cache[len(ls)][w]

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

print(pick(ls, W))

// Javascript implementation

const cache = [];

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

  if (cache[list.length] === undefined) {
    cache[list.length] = {}
  }

  if (cache[list.length][w] === undefined) {
    if (list[0][1] > w) {
      cache[list.length][w] = pick(list.slice(1), w);
    } else {
      cache[list.length][w] = Math.max(list[0][0] + pick(list.slice(1), w - list[0][1]), pick(list.slice(1), w));
    }
  }

  return cache[list.length][w];
}

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

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

0/1 Knapsack problem (Memoization)

Hint