For each of the input sets below, determine the following four things: The greed
ID: 3845046 • Letter: F
Question
For each of the input sets below, determine the following four things:
The greedy solution for the fractional knapsack problem
An optimal solution for the 0-1 knapsack problem (i.e., the maximum possible value you can take by choosing only full-complements of items and not fractions)
The greedy solution for the 0-1 knapsack problem
The “solution” to provide in each of the cases is the total value of all the items the thief will put in her knapsack.
A:
Capacity = 150
Weights <80, 60, 100, 120>
Values <100, 150, 120, 800>
B:
W = 26
Weights < 12, 7, 11, 8, 9>
Values <24, 13, 23, 15, 16>
C:
W = 170
Weights <41, 50, 49, 59, 55, 57, 60>
Values <442, 525, 511, 593, 546, 564, 617>
Explanation / Answer
A.
W = 150
Value:weight ratio = <1.25,2.5,1.2,6.67>
Greedy fractional:
120 unit weight of last item along with 30unit weight of 2nd item is the best way
Value = 6.66*120 + 2.5*30 = 875
Greedy 0-1
carry last item(120unit weight with value 800).
Unsed weight that can be carried: 30
Value:800
Optimal 0-1
carry last item(120unit weight with value 800).
Unsed weight that can be carried: 30
Value: 800
B.
W = 26
Value:weight ratio = <2,1.86,2.09,1.875,1.78>
Greedy fractional:
11unit weight of third item with 12unit weight of 1st item with 3unit weight of forth item
Value: 23 + 24 + 5.63 = 52.63
Greedy 0-1:
11unit weight of third item with 12unit weight of 1st item.
Value= 23 + 24 = 47
Optimal 0-1:
2nd 3rd and 4th item.
Value= 13+23+15 = 51
Greedy fractional is the best
C.
W = 170
Value:weight ratio = <10.78, 10.5, 10.43, 10.05, 9.93, 9.89, 10.28>
Greedy fractional:
weight of A = 1st, 2nd, 3rd and last along with 30 of 4th item
Value = 442+525+511+308.4
greedy 0-1
weight of A = 1st, 2nd, 3rd and last
Value = 442+525+511+308 = 1786cc
Bset way is greedy fractional
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.