Unbounded knapsack (Memoization)

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. Repetition of items is allowed.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Unbounded knapsack, 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:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def pick(ls, w):
  if len(ls) <= 0 or w <= 0:
    return 0
  
  global cache
  if not cache:
    cache = [[None for _ in range(w + 1)] for _ in range(len(ls) + 1)]

  if not cache[len(ls)][w]:
    take = 0

    if ls[0][1] <= w:
      take = ls[0][0] + pick(ls, w - ls[0][1]);

    skip = pick(ls[1:], w)

    cache[len(ls)][w] =  max(take, skip)

  return cache[len(ls)][w]

ls = [[10, 1], [40, 3], [50, 4], [70, 5]]
W = 8

print(pick(ls, W))

let cache = null;

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

  if (cache === null) {
    cache = [];

    for (let i = 0; i < list.length + 1; i++) {
      cache[i] = []
    }
  }

  if (cache[list.length][w] === undefined) {
    let take = 0;

    if (list[0][1] <= w) {
      take = list[0][0] + pick(list, w - list[0][1]);
    }
  
    let skip = pick(list.slice(1), w);
  
    cache[list.length][w] = Math.max(take, skip);
  }

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

const list = [[10, 1], [40, 3], [50, 4], [70, 5]];
const W = 8;

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