2

私はこの問題に取り組んでいますが、主に職場でのダウンタイムの好奇心からです。

通常の 0-1 ナップザックの問題を想像してみてください。ただし、すべてのアイテムが黄色、赤、青、または緑のいずれかであり、OCD のために、ナップザックに各色のアイテムを 2 つだけ入れる必要があります。したがって、通常のアイテムの代わりに、各アイテムには 3 つのプロパティがあります: Weight、Value、Color です。

これはまだナップザックの問題ですか、それとも別の方法で定義したほうがよいでしょうか?

4

1 に答える 1

1

nCk入力しやすいように、「n choose k」を表すために使用します。各色の項目がちょうど 2 つ必要なので、実行可能な解の数は O( nC2) で、これは O( n^2) です。各解は多項式時間で評価できるため、問題も多項式時間で解くことができます。つまり、通常のナップザックの問題よりもはるかに簡単です。

于 2012-11-20T21:08:04.220 に答える