Statement    A thief robbing a store and can carry a maximal weight of w into their knapsack. There are n items and i^th  item weigh w_i and is worth v_i 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 x_i of item i, where 0 ≤ x_i ≤ 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.