重みが W1...W4、値が V1...V4 の項目 I1、I2、I3、I4 があります。最小の重みで値を最大化したい。これは伝統的なナップザックです。ただし、一部のアイテムは一緒に使用できないという小さな制約があります。したがって、I2 と I3 は一緒に使用できないとしましょう。誰でも動的プログラミングソリューションまたは同じソリューションの他のソリューションを提供できますか?
1 に答える
2
この制約により、問題は (弱い NP 困難である個別のナップザックとは対照的に) 強力な NP 困難になります。すべてのアイテムの重量が 1 で、値が 1 であるとします。
値kを達成できるかどうかを判断すること(ナップザックの容量 >= kと仮定) は、それらの間に制約のないk 個のアイテムを見つけることと同じです。これは既知の NP 困難な問題です:独立集合.
制約の性質について追加の知識があれば、これはより簡単になる可能性があります。
于 2010-10-28T11:20:20.740 に答える