制約に関するナップザック問題

Question

私は0/1のナップザック問題に精通しています。 しかし、以下の制約が課された場合...質問を解決するにはどうすればいいですか？

1. あなたがいくつかのアイテムを選ぶなら、あなたは別のアイテム 'v'を選ぶことができないでしょう。
たとえばP> アイテムは[名前、重量、value]として与えられます。 アイテムは次のとおりです。
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50


Bを選択した場合は、A.を選択することはできません。 あなたがEを選択した場合あなたはCを選択することはできません。 Dを選択した場合、A.を選択することはできません。 同様に、制約が与えられます。


上記の問題を解決するために何らかの方法を提供してください。任意の助けが高く評価されています。

Answer 1

標準的な動的プログラミングアプローチは、この問題のために機能することはありません。この問題のために機能するつもりはないでしょう。 REL="NOFOLLOW NOREFERRER">重複サブ問題プロパティ。それでは、スレッジハンマーを抜けましょう。

これを簡単にexpore a 0-1整数線形プログラミング問題と使用シェルフのソルバー。与えられた例（そしていくつかの最大重量 $ w $ ）の場合、適切な0-1 ILPの問題は次のとおりです。

最大化 $ 20a + 80b + 30c + 70D + 50e $

$ a、b、c、d、e \ in \ {0,1 \} $
$ 10A + 50B + 20C + 30D + 50E \ LE W $
$ A + B \ LE 1 $
$ C + E \ LE 1 $
$ A + D \ LE 1 $

しかし、整数線形計画ソルバーが問題の構造を最大限に活用することは明らかではない。だから、おそらくより専門的な解決策が実際にはより良く機能するかもしれません。