knapsack problem in Javascript (Bounded & Unbounded)

The knapsack problem is inspired by a task where we are given a limited size knapsack and it must be filled with most valuable items.

We are given different items, each having a certain weight and a value, we have to pick items in the knapsack such that the values of those items are as large as possible, but their weight should be within the limit of knapsack, it should not exceed it.

There is a single constraint to this problem, you cannot break an item, either pick the complete item or don’t pick it (0-1 property).

There is another variation of this known as fractional knapsack where you can break the items.

It has two variations depending upon how we use the items.

Bounded knapsack: Items cannot be repeated.
Un-Bounded knapsack: Items can be repeated.

It is a combinatorial optimization problem and highly used in resource allocation where a task has to be chosen as a whole from a project or task under fixed budget or constraints.

Example (Bounded)

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

Output:
17

As our capacity is 15, we can add weights (4 + 1 + 10 = 15)
So the maximum value we will get is 12(4) + 1(1) + 4(10) = 17

knapsack problem in javascript

Bounded Knapsack problem in Javascript.

This problem can be solved using recursion, considering that for each item there will be two outcomes.

Pick the current item and recur for the remaining items with the reduced capacity of knapsack until the capacity becomes negative.
Leave the current item from knapsack and recur for remaining items.
Finally return the maximum value we get by picking or leaving the current item.

const knapSack = (values, weights, n, target) => {
  //base case: when we cannot have take more items
  if(target < 0){
    return Number.MIN_SAFE_INTEGER;
  }
  
  //base case: when no items are left or capacity becomes 0
  if(n < 0 || target === 0){
    return 0;
  }
  
  // pick current item n in knapSack and recur for
  // remaining items (n - 1) with reduced capacity (weight - weights[n])
  let include = values[n] + knapSack(values, weights, n - 1, target - weights[n]);

  // leave the current item n from knapSack and recur for
  // remaining items (n - 1)
  let exclude = knapSack(values, weights, n - 1, target);
  
  // return maximum value we get by picking or leaving the current item
  return Math.max(include, exclude);
}

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

console.log(knapSack(values, weights, values.length - 1, target));

Output:
17

Time complexity: O(2 ^ n).
Space complexity: O(1).

Using dynamic programming to solve the Bounded knapsack problem in Javascript

As this problem is exhibiting both the properties of DP, i.e optimal substructure and overlapping subproblems, which means we can break down the problems in sub-problems and store their result so that we can reuse them.

Top-down approach (Recursive)

We use Hashmap to cache the result of the already solved subproblems using a key and then before solving the sub-problems first check if its already solved then use that value, else solve it and store it.

const knapSack = (values, weights, n, target, lookup) => {
  // base case: when we cannot have take more items
  if (target < 0) {
    return Number.MIN_SAFE_INTEGER;
  }

  // base case: when no items are left or capacity becomes 0
  if (n < 0 || target == 0) {
    return 0;
  }

  // form a unique key from the inputs for memoization
  const key = `${n}|${target}`;

  // If the sub-problem is appearing for first time, solve it and
  // store its result in the map
  if (!lookup.has(key)){

    // pick current item n in knapSack and recur
    // for remaining items (n-1) with reduced capacity (target - weights[n])
    let include = values[n] + knapSack(values, weights, n - 1, target - weights[n], lookup);

    // leave current item n from knapSack and recur for
    // remaining items (n-1)
    let exclude = knapSack(values, weights, n - 1, target, lookup);

    // Assign max value we get by picking or leaving the current item
    lookup.set(key, Math.max(include, exclude));
  }

  // return the value
  return lookup.get(key);
}

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;
let lookup = new Map();

console.log(knapSack(values, weights, values.length - 1, target, lookup));

Output:
17

Time complexity: O(values.length * target).
Space complexity: O(values.length * target).

Bottom-up approach (Iterative)

const knapSack = (values, weights, target) => {
  // T[i][j] holds the max value of knapsack
  let T = new Array(values.length + 1);
  for(let i = 0; i < T.length; i++){
    T[i] = new Array(target+1).fill(0);
  }

  // for ith item
  for (let i = 1; i <= values.length; i++) {
    // choose all weights from 0 to maximum capacity W
    
    for (let j = 0; j <= target; j++) {
      // base case: don't pick ith element if j-weights[i-1] is negative
      if (weights[i-1] > j) {
        T[i][j] = T[i-1][j];
      } else {
        // store the max value that we get by picking or leaving the i'th item
        T[i][j] = Math.max(T[i-1][j], T[i-1][j-weights[i-1]] + values[i-1]);
      }
    }
  }

  // return maximum value
  return T[values.length][target];
}

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

console.log(knapSack(values, weights, target));

Output:
17

Time complexity: O(values.length * target).
Space complexity: O(values.length * target).

Unbounded knapsack problem problem

Example

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

Output:
39

As our capacity is 15 and we can repeat the items, we can add weights (4 + 4 + 4 + 2 + 1 = 15)
So the maximum value we will get is 12(4) + 12(4) + 12(4) + 2(2) + 1(1) = 39

As we can repeat the same item again and again in unbounded knapsack, using this condition in mind we can come up with the following recurrence relation.

Create a lookup table, lookup[target + 1] which can be used such that lookup[i] stores the maximum value which can be achieved using all items and i'th capacity of knapsack.

lookup[target + 1].fill(0);

from j = 0 to j = n - 1
lookup[i] = max(lookup[i], lookup[i-weight[j]] + val[j])
                   where j varies from 0 
                   to n-1 such that:
                   weights[j] <= i

result = lookup[target]

const unboundedKnapsack = (values, weights, n, target) => {
  // create a lookup table
  // lookup[i] is going to store maximum value
  // with knapsack capacity i.
  const lookup = new Array(target + 1).fill(0);

  // fill lookup[] using above recursive formula
  for(let i = 0; i <= target; i++){
    for(let j = 0; j < n; j++){
      if(weights[j] <= i){
        lookup[i] = Math.max(lookup[i], lookup[i - weights[j]] + values[j]);
      }
    }
  }
  
  //return the max
  return lookup[target];
}

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

console.log(unboundedKnapsack(values, weights, values.length - 1, target));

Output:
39

Time complexity: O(values.length * target).
Space complexity: O(target + 1).