Проблема с рюкзаком с ограничениями на стоимость предметов

Question

Данный $n$ предметы с весом $w_1,...,w_n$ и ценности $v_1,...,v_n$, и ограничение по весу $W$, целью по-прежнему является максимизация общей стоимости перевозимых предметов (при этом не превышая предельного веса).Теперь новым ограничением является, как только элемент со значением $v_i$ берутся все предметы, стоимость которых превышает $v_i$ тоже нужно принимать.(Можно предположить, что все $v_i$они разные)

Моя цель состоит в том, чтобы достичь этого в $O(n)$ время, и вот моя попытка (предположим, что входные данные представляют собой массив $A$ из кортежей $(w_i, v_i)$):

1. Рассчитайте общий вес предметов: $W_{\mathrm{total}}\получает \sum_{i=1}^n w_i$;

2. в то время как $(W_{\mathrm{всего}} > W)$ делай:

   2.1 $p\получает$ медиана значений в $A$;

   2.2 $R\получает$ предметы, стоимость которых превышает $p$;

   2.3 $L\получает\setminus R$;(товары, стоимость которых меньше, чем $p$)

   2.4 $W_R\получает$ $\sum_{A[i]\в R}w_i$;

   2.5 $W_{\mathrm{total}}\получает W_R$;

   2.6 $A\получает R$;

3. $W\получает W- W_{\mathrm{итого}}$;(оставшаяся емкость)

4. Повторите шаг 2 для массива $L$, генерирующий массив $L'$;

5. Возврат $L'\чашка A$;

Обратите внимание, что алгоритм нахождения медианы требует линейного времени.

Я предполагаю, что мой алгоритм стоит $O(n)$ с тех пор для каждой итерации в каждом цикле while размер входных данных уменьшается вдвое, но я не уверен в этом на 100%.Итак, действительно ли этот алгоритм требует линейного времени?Если нет, то какие поправки можно внести или есть ли общая идея для разработки такого алгоритма, который требует линейного времени?Любая помощь будет высоко оценена!:)

Answer 1

Да, ваш алгоритм выполняется в $O(n)$ время, если вы используете алгоритм медианы медиан.Вы можете доказать это себе, посмотрев на свой алгоритм и отметив, что в каждом цикле размер рассматриваемого нами массива сокращается вдвое.И время выполнения тела цикла равно $O(n)$ (если мы используем медиану медиан и копирование / фильтрация массива выполняется $O(n)$ во всяком случае).Теперь мы получаем следующую сумму:

$$\sum_{i=0}^{\log (n)} \frac{n} {2^ i} \leq \sum_{i=0}^{\infty} \frac {n} {2^ i} = n\cdot\sum_{i=0}^{\infty} \frac{1}{2 ^ i} = 2n \in O(n)$$

Тот Самый $\log(n)$ это связано с тем фактом, что вы можете разделить только размер массива $log(n)$ делите время пополам, пока не достигнете $1$ (потому что $2^{\log(n)} = n$).Каждый член суммы выражает стоимость одного выполнения тела цикла.