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

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def pick(ls, w):
  cache = [{} for _ in range(len(ls) + 1)]

  for i in range(len(ls) + 1):
    for j in range(w + 1):
      if i == 0 or j == 0:
        cache[i][j] = 0
      elif ls[i - 1][1] > j:
        cache[i][j] = cache[i - 1][j]
      else:
        cache[i][j] = max(ls[i - 1][0] + cache[i - 1][j - ls[i - 1][1]], cache[i - 1][j])

  return cache[len(ls)][w]

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

print(pick(ls, W))

// Javascript implementation

function pick(list, w) {
  const cache = [];

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

    for (let j = 0; j < w + 1; j++) {
      if (i == 0 || j == 0) {
        cache[i][j] = 0;
      } else if (list[i - 1][1] > j) {
        cache[i][j] = cache[i - 1][j];
      } else {
        cache[i][j] = Math.max(list[i - 1][0] + cache[i - 1][j - list[i - 1][1]], cache[i - 1][j]);
      }
    }
  }

  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 (Tabulation)

Hint