Knapsack Problem

• A collection of items have different values and weights, optimize the amount of value you can carry when you have a knapsack with a limited carrying weight
• Variations
  • Bounded: Can only take one of each item
  • Unbounded: Can take multiple of one item
  • Fractional Items: Can take part of an item
  • One/Multiple Knapsacks
• 0-1 Knapsack Problem
  • Items are bounded, non-fractional, and only one knapsack
  • Brute Force
    • Check every possible combination within the weight limit for the max value
    • $O(2^n)$
      • $2^n$ combinations of sets for N-items in a set (the cardinality of the power set)
  • Greedy Algorithms
    • Order all the elements by value / weight
    • Try to fill the knapsack with the top elements if they fit until the bag is full or there are no elements left
    • Will always work for fractional knapsack, but not always otherwise
  • Dynamic
    • opt function (the recurrence relation)
      • Meaning
        • optimal value of max weight subset that uses items $1,\dots ,i$ with weight limit
        • If we have i items and a Knapsack of capacity W, what is the optimal value?
      • Usage
        • The outputs of this function can be visualized as a table where the rows are the number of items and the columns are the weights
        • Fill out the entire table using the relation and then find the maximum cell
        • Finding which items we selected
          • Go to the max item
          • If the cell in the row above is different than that item is part of the answer
            • If not, just keep going up
          • Subtract the weight of that item and then move to the column and repeat the process
      • $\text{opt}(i,W)$:
        • if i = 0: $0$
        • if $w_i>w_k$: $\text{opt}(i-1,W)$
        • otherwise: $\max (\text{opt}(i-1,W),v_i+\text{opt}(i-1,W-w_i))$