標準0/1ナップザックでは、すべてのアイテムの重量が他のアイテムとは独立している必要があります。 DPは、このソリューションに向けた効率的なアルゴリズムです。しかし、今、私は新しいアイテムの0/1ナップザックと従属項目の重量？
重量はすでに ナップザックの前の項目に依存していることを、この問題の類似しているが、拡張子に会いました。
は、たとえばのために、私たちは5つの項目a、重量w_aとb、c、dとe、...、w_eを持っています。項目bおよびcは重量依存性を有する。 bはナップザックに既に存在する場合、それは、bで即ちweight(b&c) < w_b + w_cをいくつかの領域を共有することができるので
、項目cの重量は、小さいw_c以上であろう。対称的に、cがすでにナップザックに入っている場合、bの重量はw_bより小さくなります。
この不確かさは、元のDPアルゴリズムの失敗をもたらします。なぜなら、これは以前の反復の正確さに依存するためです。私はナップザックに関するいくつかの論文を読んだが、利益（二次ナップザック問題）に従属するか、またはランダム分布（確率的ナップザック問題）に従った可変重量を持つ依存関係を持っている。私は前の質問1/0 Knapsack Variation with Weighted Edgesも知っていますが、非常に一般的な答えしかありません。このナップザックの名前は何であるかについての答えはありません。
一つの既存のソリューション：
私はまた、彼らはgroup the related items as one combined item for knapsack DBMSの最適化、およそa paper内の1つの近似解を読みました。この技術をこの例で使用する場合、ナップザックの項目はa,bc,d,eとなるため、これらの4つの項目のうちの2つの間には依存関係がありません。しかし、an item with "small weight and benefit" is grouped with another item with "large weight and benefit"のように最適な結果を得られない例を作るのは簡単です。この例では、「小さい」項目は解決策では選択しないでくださいが、「大きな項目」と一緒に選択します。
質問：
、または少なくともいくつかのエラーを保証して最適な結果を得ることができ、効率的な解決手法のいずれかの種類がありますか？あるいは、私はこの問題のモデル化に間違った方向を取っていますか？
あなたの質問のようにいくつかdownvotesがあるようです。私はdownvotersには本当に同意しませんが、それはおそらくあなたがトピックからオフの "オフサイトのリソース"を求めるように解釈することができるこの問題の研究があるかどうか尋ねたからです。 – samgak
@samgakコメントをいただきありがとうございます。私は可能な解決策にもっと焦点を当てるように私の質問を修正しました。 –
この質問は[メタで議論されている]（http://meta.stackoverflow.com/q/332155/2840103）です。 – johnnyRose