Проблема Knaxackack с точным необходимым ограничением номера предмета

Question

Как бы мы решили проблему knaxackack, если теперь мы должны исправить количество элементов в knaxackack с постоянным $ l $ ?Это та же проблема (максимальная масса $ W $ , каждый элемент имеет значение $ v $ иВес $ W $ what ), но вы должны добавить именно $ l $ item(ы) к рюкзаке (и, очевидно, нужно оптимизировать общее значение knaxackack).

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

Редактирование: Я ищу псевдо- полиномиальные временные решения

Answer 1

Вы можете преобразовать эту проблему в экземпляр knaxack. Пусть $ n $ Будьте количество элементов, $ v $ - максимальное значение элемента и предположим, что каждый элемент весит на большинстве $ W $ (в противном случае его можно отбросить).

Чтобы убедиться, что вы выбираете, по крайней мере, $ l $ Элементы:

.
• Добавить $ n (v + 1) $ к значению каждого элемента.
• Теперь проблема эквивалентна максимальному количеству выбранных элементов, нарушающих галстуки в пользу набора предметов с наибольшим исходным общем значением, при условии ограничения веса. Существует решение, которое выбирает, по крайней мере, $ l $ items IFF Оптимальное решение имеет значение, по меньшей мере, $ n (v +1) l $ .

Чтобы убедиться, что вы выбираете на большинстве $ l $ Элементы:

.
• Добавить $ (w + 1) $ на вес каждого элемента.
• Добавить $ l (w + 1) $ на $ W $ .
• Теперь каждое подмножество большего количества $ l $ Events весит как минимум $ (l + 1) (w + 1 )= L (w + 1) + (w + 1)> l (w + 1) + w $ и, следовательно, не выполнимо. Каждое подмножество $ l $ элементы, имеющие общий вес $ W $ , теперь весит $ l (w + 1) + w $ , и, следовательно, это возможно, IFF $ W \ Le w $ . Подмножество с менее чем $ l $ элементы могут быть выполнены, даже если его общий вес больше, чем $ w $ Однако его общая стоимость всегда будет меньше, чем $ n (v + 1) l $ .