Problem

Given a set of items, each with a weight and a value. Determine the maximum value of items to include in a collection so that the total weight is less than or equal to a given limit

Example

Given 3 items with weights = {10, 20 , 30} and values = {60, 100, 120} respectively, knapsack weight capacity is 50. The maximum value of items to include in the knapsack is 220

Dynamic programming approach

Have 2 options at each collecting step

  • Including the i item if not exceeding the weight limit
  • Excluding the i item if exceeding the weight limit

Implementation

Fill up a cache matrix int[][] cache = new int[N+1][W+1] with

  • 0 to N items as columns
  • 0 to W weight-limit as rows
  • each matrix cell cache[i][w] is the maximum value can be attained with weight less than or equal to w using i items

  • i is the current item
  • w is the current weight limit
  • weights[i-1] is weight of current item as int[] weights is 0 based index
  • values[i-1] is value of current item as int[] values is 0 based index
  • cache[i][w] is maximum value of current item as int[][] cache is 1 based index
  • weights[i-1] > w weight of the current item is more than the weight limit
  • cache[i][w] = cache[i-1][w] excludes the current item
  • cache[i-1][w-weights[i-1]] + values[i-1] includes the current item

References