**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

There are two versions of problem

Fractional knapsack problemThe 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

xof item_{i}i, where 0 ≤x≤ 1._{i }Exhibit greedy choice property.

Exhibit optimal substructure property.

- Greedy algorithm exists.

- ?????
0-1 knapsack problemThe 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.

Exhibit optimal substructure property.

- No greedy algorithm exists.

- Only dynamic programming algorithm exists.