Жадный алгоритм для заданного несортированного ввода с временной сложностью nlogn

Задача о рюкзаке с несколькими ограничениями

У меня есть такой пример, я просто пытаюсь понять, в чем разница между жадным алгоритмом с O (n * logn) и жадным алгоритмом для O (n2)? Я правда не знаю с чего начать помогите пожалуйста! Сортировка или что-то другое :(? (Соотношение прибыли и веса не в порядке убывания или увеличения, совершенно случайно) p = (p1;:::; pn) = (24; 17; 95; 103; 41; 39; 22; 1) w = (w1;:::; wn) = (20; 15; 39; 41; 27; 23; 18; 2)


knapsack-problem greedy
person user2333464    schedule 29.04.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Да, алгоритм O (n log n) состоит в том, чтобы отсортировать по (прибыль / вес) в порядке убывания, а затем захватить как можно больше объектов до предела веса. Конечно, алгоритм сортировки должен быть O (n log n).

Наивный (O (n ^ 2)) алгоритм будет заключаться в том, чтобы многократно искать в списке элемент с наивысшим соотношением (прибыль / вес) и брать его. Обратите внимание, что это, по сути, то же самое, что и сортировка по выбору.

person Imre Kerr    schedule 29.04.2013
comment
Большое спасибо за ваш ответ, правда, я искал целый день, и я спрашивал об этом своего профессора, но до сих пор всегда находил сложные ответы, это не может быть так просто, просто такой чистый ответ! Еще раз большое спасибо! - person user2333464; 30.04.2013