アルゴリズム2つの制限付きナップザック

Question

Iv'eはプロジェクトで作業していましたが、次のようなシナリオが発生しました： M> Nの2つのボックスを選択する必要があります。 ：

は

• 我々は同じボックスのIDを選択することはできません同じボックスの色
• を選択することはできません

ボックスがトップ

上の最大の重みでソートしています0

最高の重み付けRed1から始まるNaiveアルゴリズムで（Red1、Blue2）を選択しました。同じID 1を持っているためBlue1を追加できませんでした.Red Box 10のウェイトで11の総重量で終わりましたが、Blue1を選択した場合、18.9で終わる可能性があります& Red2 Nは2より大きい可能性があります。

NP困難な問題ですか？ 優れた実行時間効率を備えたソリューション

Answer 1

私たちは、だから、M、N、色とidのためどのように大きな制約に依存して複雑O(M choose N)

で複雑O(2^color * 2^id * M * N)やバックトラック+剪定とDPソリューションを使用することができます。