Greedy algorithm Question Please show work Consider a greedy algorithm for activ
ID: 3668296 • Letter: G
Question
Greedy algorithm Question Please show work
Consider a greedy algorithm for activity section that picks the activity with the smallest duration time. Show that this algorithms does not solve the activity selection problems correctly. Give an example that shows the greedy algorithms that sorts with respect to profit/weight ratio does not solve the 0 - 1Knapsack problem. Give an example that shows the greedy algorithms that picks the item with largest profit does not solve the 0 - 1Knapsack problem.Explanation / Answer
Definition of knapsack problem:
Item name
Weight
Value in $
Gold Bars 100 grams each
100 grams = 0.1 kg
3900
Silver Bars 1 kg each
1 kg
495
Mercury bottles 1 kg each
1 kg
45
Rice 10 kg bags each
10 kg
3
Gold bars 1kg each
1 kg
39,000
Item name ( sorted by most expensive to cheapest)
Weight
Value in $
Available quantity
Gold bars 1kg each
1 kg
39,000
20 kg
Silver Bars 1 kg each
1 kg
495
30 kg
Mercury bottles 1 kg each
1 kg
45
50 kg
Rice 10 kg bags each at the rate of 30 cents per kilo
10 kg
3
200 kg
Item name
Weight
Value in $
Gold Bars 100 grams each
100 grams = 0.1 kg
3900
Silver Bars 1 kg each
1 kg
495
Mercury bottles 1 kg each
1 kg
45
Rice 10 kg bags each
10 kg
3
Gold bars 1kg each
1 kg
39,000
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.