4 votes 4 votes Show how to solve the fractional knapsack problem in $O(n)$ time. Algorithms algorithms greedy-algorithm + – Prince Sindhiya asked Jul 22, 2018 edited Jul 22, 2018 by Prince Sindhiya Prince Sindhiya 1.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply Prince Sindhiya commented Jul 23, 2018 reply Follow Share @abhishek i got this soln for above question ,please explain it if u understand. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes I think we cant do in O(n) time Find price / weight (P/W). Which will take constant time we need to sort them which will take O(nlogn). Now we select one by one .... So overall it will take O(nlogn) Using min heap also it will take O(nlogn) abhishekmehta4u answered Jul 22, 2018 abhishekmehta4u comment Share Follow See all 2 Comments See all 2 2 Comments reply Prince Sindhiya commented Jul 22, 2018 reply Follow Share @abhishek ,u are correct that it will be $O(nlogn)$ using heap and Also using comparison based sorting like merge sort but this question is given in coreman to show ,i edited the question see it . 1 votes 1 votes abhishekmehta4u commented Jul 23, 2018 reply Follow Share @Prince Soln is given ??? 0 votes 0 votes Please log in or register to add a comment.