約束揹包不重

Question

我只是碰到下面的問題就來了（這讓我想起揹包-問題的，但是也有一些區別）：

現在給你的項目數量爲n的，你必須把裏面的你具有最大利潤的揹包。每個項目都有一個特定的利潤值和一個特定的形狀。由於它們的形狀，一些物品不能一起放入揹包。與普通揹包問題不同，沒有最大重量限制揹包中物品的數量。 您還會得到每個項目的清單。在該列表中，您可以看到可以放入揹包中的物品以及相應的物品。

是否有一種算法可以計算出最優解？ 還是NP完全問題？在那種情況下，有沒有一種近似方法？

Answer 1

我認爲這是NPC。

polynomial verification requirement是微不足道的。

該減少是對Maximal Independent Set的問題。對於每個MIS實例G =（V，E），構建一組項目V各自具有單位利潤。對於每個項目v ∈ v，它可以放置的項目列表是它不共享邊的頂點集。即，如果G（v）是可以與v，然後G（v）= {w | （u，w）∉ E}。

如果存在與利潤ķ解決新問題，那麼它使用ķ項目不在對方的名單。由此可見，對於獨立集合問題有一個解決方案的大小爲k。