Knapsack Problem

 

Statement    A thief robbing a store and can carry a maximal weight of w into their knapsack. There are n items and ith  item weigh wi and is worth vi dollars. What items should thief take?

There are two versions of problem

  1. Fractional knapsack problem
    The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.
      Exhibit greedy choice property.
      • Greedy algorithm exists.
      Exhibit optimal substructure property.
      • ?????
  2. 0-1 knapsack problem
    The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.
      Exhibit No greedy choice property.
      • No greedy algorithm exists.
      Exhibit optimal substructure property.
      • Only dynamic programming algorithm exists.