Question

1 (a): Give an example that shows the greedy algorithm that picks the item with largest profit first (and continues in that fashion) does not solve the 0 − 1 Knapsack problem.

1 (b): Give an example that shows the greedy algorithms that picks the object with largest profit first (and continues in that fashion) does not solve the Fractional Knapsack problem.

Please show your work! I will rate quality answers. Thank you!

Answer 1

Two main kinds of Knapsack Problems:
1.0-1 Knapsack

* N items (can be the same or different)

* Have only one of each

*Must leave or take (ie 0-1) each item (eg ingots of gold)

*DP (Dynamic programming )works, greedy does not

2.Fractional Knapsack

*N items (can be the same or different)

*Can take fractional part of each item (eg bags of gold dust)

*Greedy works and DP algorithms work

1 a). Greedy doesn't work for 0-1 Knapsack Problem:

Example 1: Knapsack Capacity W = 25 and
Item   A   B   C   D
Price   12   9   9   5
Size   24   10   10   7

Optimal: B and C. Size=10+10=20. Price=9+9=18
Possible greedy approach: take largest Price first (Price=12, not optimal)
Possible greedy approach: take smallest size item first (Price=9+5=14, not optimal)

1b) greedy algorithms that picks the object with largest profit first (and continues in that fashion) does solve the Fractional Knapsack problem.

Item   A   B   C   D
Value   50   140   60   60
Size   5   20   10   12
Ratio   10   7   6   5

Solution:
All of A, all of B, and ((30-25)/10) of C (and none of D)
Size: 5 + 20 + 10*(5/10) = 30
Value: 50 + 140 + 60*(5/10) = 190 + 30 = 220

Time: Θ(n), if already sorted