Несколько рюкзак, вес = прибыль

Question

У меня есть исследование проблем рюкзака. Теперь я остановился на специальном типе проблемы с несколькими рюкзаками, где вес каждого элемента равен прибыли этого элемента.

Я не могу найти ни одной бумаги, говорящей о сложности этой проблемы. Это NP-полный или нет?

Любая помощь будет оценена по достоинству.

Answer 1

Я нашел проблему, которая может быть сведена к моей - Проблема с множеством подмножеств. Задача множественного подмножества (MSSP) - это выбор предметов из заданного набора грунта и их упаковка в заданное количество идентичных контейнеров, так что сумма весов элементов в каждом бункере не превышает емкость ящика и общую сумму вес упакованных предметов как можно больше. Это может быть легко сведено к моей проблеме. Это доказывает, что моя проблема NP-hard.

Answer 2

Эта проблема NP-hard через сокращение от заданной проблемы раздела. В этой задаче вам задан набор целых чисел, и их спрашивают, можно ли разбить этот набор на два набора с одинаковой суммой. Вы можете уменьшить его до своей проблемы следующим образом: если у набора есть сумма 2k, создайте два рюкзака с пропускной способностью k каждый и создайте один элемент для каждого числа в наборе для разделения. Тогда любой способ полного заполнения рюкзаков соответствует разбиению исходного множества и наоборот. (Если сумма чисел нечетна, просто сопоставьте экземпляр проблемы с неразрешимым экземпляром проблемы с рюкзаком).

Надеюсь, это поможет!