Сведение задачи о ранце к обратной задаче

Question

1) Предположим, у нас общая проблема с ранцем 0-1.Для заданного набора из n элементов, пронумерованных от 1 до n, каждый из которых имеет вес w_i и значение v_i, а также максимальный весовой коэффициент W. Здесь нам нужно выбрать несколько объектов, чтобы максимизировать сумму v_i, чтобысумма w_i выбранных объектов не будет превышать заданное число W.

       maximize∑(v_i*x_i), such that ∑(w_i*x_i)≤ W

2) Теперь предположим, что у нас точно такая же проблема, но нам нужно выбрать объекты так, чтобы сумма их значений была минимальной,и сумма их весов не может быть меньше заданного числа.

      minimize∑(v_i*x_i), such that ∑(w_i*x_i)≥ W.

Зная, что первая задача выполнена NP, как я могу доказать, что вторая имеет такую ​​же сложность, другими словами, NP завершена?тоже?

Answer 1

Зная, что первая задача завершена, NP, как я могу доказать, что вторая имеет ту же сложность, другими словами, тоже завершена NP?

Если вы хотите доказать, что задача B является NP-полной, вы должны доказать, что существует полиномиальное сокращение времени с A до B, где, как известно, A является NP-полной проблема.
Сокращение полиномиального времени от проблемы A к проблеме B - это алгоритм, который решает проблему A, используя полиномиальное количество вызовов подпрограммы для задачи B и полиномиальное время вне этих вызовов подпрограммы. ( источник ).

Таким образом, в вашем случае вы можете легко уменьшить полиномиальное время от задачи о рюкзаке до задачи с обратным рюкзаком.
Эти две проблемы эквивалентны (поиск оптимального решения одной немедленно решает другую).
Пусть S будет набором объектов, M будет суммой весов объектов S и W вместимость рюкзака. Тогда имеем:

• (i) поиск подмножества объектов таким образом, чтобы сумма их веса не превышала W, а сумма их значений была максимальной

эквивалентно

• (ii) поиск подмножества объектов таким образом, чтобы сумма их веса была не менее M-W, а сумма их значений была минимальной.

Это потому, что если S' является оптимальным решением (i), то S\S' является оптимальным решением (ii) (и наоборот).

Это сокращение за полиномиальное время (O(1) вызовы подпрограммы, полиномиальное количество операций), поэтому обратный рюкзак действительно NP-завершен.

Answer 2

Ключевой идеей, по-видимому, является обмен значения и веса и использование бинарного поиска по второй проблеме для построения сокращения.

Учитывая экземпляр I первой формулировки со значениями v_i и весамиw_i, создайте экземпляр второй проблемы, обмениваясь прибылью и весом.Сумма всех весов (которые теперь являются прибылью) ограничена

n * w_max

, где w_max - максимальный вес.Само это число экспоненциально в длине кодирования входа;тем не менее, мы можем использовать бинарный поиск, чтобы определить максимально достижимую прибыль, чтобы начальная емкость W не была превышена.Это можно сделать за

log( n * w_max )

итераций, число, которое полиномиально ограничено размером кодирования ввода, используя то же количество вызовов алгоритма для второй задачи.Описанный алгоритм представляет собой полиномиальное перетекание из первой задачи ко второй.

Answer 3

Обратный рюкзак - один из моих любимых.Хотя я никогда не доказывал, что он полностью завершен, я знаю, как переформулировать вопрос к самой проблеме с рюкзаком, что должно помочь:

Вместо того, чтобы добавлять объекты в пустой пакет, рассмотрим проблемувыбора предметов, которые будут удалены из сумки, которая полна.Тогда, поскольку количество весов не может быть меньше данного числа, мы должны удалить только до общего (минимальный вес веса) в терминах объектов.

Поскольку цена должна быть минимизирована, тоцена удаляемых предметов должна быть максимальной.

У нас осталась начальная проблема с рюкзаком, когда мы должны выбрать группу предметов (подлежащих удалению) таким образом, чтобы мы максимизировали их цену, а их общий вес не превышал минимальный весовой вес.(В конце мы берем предметы, которые мы НЕ удаляли, как решение)

Мы реформировали проблему так, чтобы она была точно оригинальной проблемой с рюкзаком, поэтому она также должна быть NP-полной.

Прелесть этого метода в том, что я лично понятия не имею, что NP завершает;Я только что доказал, что обратный рюкзак и рюкзак абсолютно эквивалентны.