Knapsack

Introduction

Knapsack problems are perfect illustrations of the spirit of dynamic programming. Optimization problems => optimal substructures. And the constraints and the price table will usually give some overlapping recursive calls.

Types

• 0/1 Knapsack (size)

  • doability

  • number of ways

  • subsets

• 0/1 Knapsack (size and value)

• Multi-constraint Knapsack

• Combination Knapsack

• Infinite Knapsack

References

• Wikipedia - Knapsack Problem

• Wikipedia - Continuous knapsack problem

• Backpack I to VI by linspiration

• 9 lessons on pack by Tianyi Cui