Greedy algorithm for a given unsorted input with time complexity "nlogn"

Question

Multi-Constrained Knapsack Problem

i have such a given example ,i m just trying to understand, whats the difference between greedy algorithm with O(n*logn) and greedy algorithm for O(n2)? I really do not know how to start please help! Should i sort it or something different :( ? (profit and weight ratio is not in a decreasing or increasing order,totally random) p = (p1; : : : ; pn) = (24; 17; 95; 103; 41; 39; 22; 1) w = (w1; : : : ;wn) = (20; 15; 39; 41; 27; 23; 18; 2)

Answer 1

Yup, the O(n log n) algorithm is to sort by (profit / weight) in decreasing order, and then grab as many objects as possible up to the weight limit. Of course the sorting algorithm has to be O(n log n).

The naive (O(n^2)) algorithm would be to repeatedly search the list for the item with the highest (profit / weight) ratio and grab that. Note that this is, in effect, the same as doing a selection sort.