edited by
1,018 views

1 Answer

2 votes
2 votes

I think we cant do in O(n) time

  1. Find price / weight  (P/W). Which will take constant time 

  2.  we need to sort them which will take O(nlogn).

  3. Now we select one by one ....

So overall it will take O(nlogn) 

  • Using min heap also it will take O(nlogn)

Related questions

1 votes
1 votes
1 answer
1
Aarvi Chawla asked Jun 19, 2018
2,834 views
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 prob...