Проблема Knaxackack NP-Hard, когда $ v_i= i $?

Question

Проблема knaxackack - это NP-труд и может быть сформулирована как: $$ \ begin {aligin} & \ text {maximize} \ sum_ {i= 1} ^ n v_i x_i, \ tag {p1} \\ \ Text {С учетом} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {и} x_i \ in \ {0,1 \}. \ end {align} $$

Что если $ v_i= i $ ?Это все еще NP-HARD?

$$ \ begin {align} & \ text {maximize} \ sum_ {i= 1} ^ n ix_i, \ tag {p2} \\ & \ Text {С учетом} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {и} x_i \ in \ {0,1 \}. \ end {align} $$

Я пытаюсь уменьшить (P1) до (P2).Учитывая экземпляр (P1), я создаю одинаковое количество предметов, одинаковых весов.Теперь я должен связать решения (P1) и (P2).

Answer 1

Нет, эта проблема в $ \ mathbf {p} $ . Основной точкой является то, что сумма всех значений составляет $ 1 + 2 \ LDOTS + N=FRAC {N (N + 1)} {2}=Mathcal {o} ( n ^ 2) $ , который является полиномом в размере ввода. Без дополнительного ограничения $ v_i= i $ , сумма всех значений может быть экспоненциальной в размере ввода, поскольку значения представлены в двоичном режиме на входе.

Итак, мы можем определить $ dp [i] [v] $ , где $ 1 \ leq i \ leq n $ и $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , чтобы быть минимальным весом, необходимым для получения значения По меньшей мере, $ V $ , используя только первый $ i $ элементы. Если его нельзя достичь, мы установим $ dp [i] [v]= inf $ . Окончательный ответ - это максимальный $ v $ такой, что $ dp [n] [v] \ leq w $ .

Значения DP могут быть рассчитаны следующим образом:

$ dp [i] [v]=min (dp [i-1] [v], w_i + dp [i-1] [v - v_i]) $ .

Первый термин считает возможностью $ i ^ {th} $ элемент, который не выбран, а второй термин - это возможность того, что она выбрана. < / P >.

Таким образом, вся проблема может быть решена в $ \ mathcal {o} (n ^ 3) $ time и $ \ mathcal {o} (n ^ 3) $ пространство, которое можно уменьшить до $ \ mathcal {o} (n ^ 2) $ Просто повторное использование двух массивов размеров $ \ frac {n (n + 1)} {2} + 1 $ .