1 Тема от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Тема: Непрерывная задача о рюкзаке

В Кормене, в главе о жадных алгоритмах есть такое упражнение:

• 16.2-6. Покажите, как решить непрерывную задачу о рюкзаке за время О (n). (во втором русском издании оно находится на странице 458)

Если кто не знает, то суть задачи следующая: есть N кучек золотого песка, i-ая кучка имеет вес Wi и стоимость за всю кучку Ci; также есть рюкзак в который помещается не более W килограммов песка; нужно унести какой-то песок(кучки можно брать не полностью), чтобы его суммарная стоимость была максимальна.

За O(n log n) решение конечно очевидно, а вот за O(n) непонятно; честно говоря вообще сомневаюсь, что это возможно. Есть идеи?

2 Ответ от ivank

  • ivank
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 11

Re: Непрерывная задача о рюкзаке

Дам две подсказки:

1) За линейное время ты можешь найти в массиве медиану (9-я глава в CLRS), а значит и разбить любой массив пополам, так чтобы в одной половинке элементы были меньше чем в другой

2) T(n) = T(n/2) + O(n) имеет решение O(n).