2,832 views
1 votes
1 votes
Show how to solve the fractional knapsack problem in O(n) time.

The solution include that we can find the median in O(n) time and then solving the fractional knapsack problem on input of size n/2, but the pi/wi is not sorted, so how do we have the equation T(n) = T(n/2) + cn?

1 Answer

Best answer
2 votes
2 votes
First find the ratio(profit/weight)= O(n) time

Then find median(using selection procedure)= O(n) time

Then sum the weights of all items whose value exceeds the median and call it M. If M exceeds W then we know that the solution to the fractional knapsack problem lies in taking items from among this collection. In other words, we’re now solving the fractional knapsack problem on input of size n/2. On the other hand, if the weight doesn’t exceed W, then we must solve the fractional knapsack problem on the input of n/2 low-value items, with maximum weight W − M

so the recurrence relation T(n) = T(n/2) + cn..
selected by

Related questions

0 votes
0 votes
0 answers
1
Aarvi Chawla asked Jun 14, 2018
582 views
Give an O(n lgk)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in the input lists. Use a min heap for k-way merging...
4 votes
4 votes
1 answer
2
Prince Sindhiya asked Jul 22, 2018
1,018 views
Show how to solve the fractional knapsack problem in $O(n)$ time.
0 votes
0 votes
0 answers
3
Aarvi Chawla asked Jun 14, 2018
349 views
Argue that for any constant 0<α≤1/2, the probability is approximately 1−2α that on a random input array, PARTITION produces a split more balanced than 1−α to α....
0 votes
0 votes
1 answer
4
dragonball asked Jun 22, 2017
369 views
While solving this recurrence T(n) = 2T(n/2 + 17) + n what is the need of 17 and how to go forward to solve this question using the method of master theorem ?