相互排他的なアイテムを含むナップザック

Question

標準的なナップザックの問題はダイナミックプログラミングで解決できますが、私の考えを少しでも解消しようとしていますが、思ったより難しいかもしれません。

オリジナルナップザック問題はサイズW、そして最高の合計値とのナップザックに収めることができるアイテムのサブセットを見つける重量w[i]と値v[i]を持ち、項目のリストでナップザックを与えられたということです。

これは動的プログラミングのO(Wn)で行うことができます。nはアイテム数です。

今私は m制約を追加しようとした場合、それらのそれぞれが唯一の相互排他的に撮像することができるアイテムのペアである（つまり、アイテムAとアイテムBの制約が存在する場合は、その後、私は取ることができ

---

いずれか1つではなく、両方ではない）

このような制約の下で、この問題は動的プログラミングによって解決できますか？O(Wn)？

Answer 1

仮定：各要素は、1つの制約のなかに含まれています。
1.項目が溶液
2ザに含まれる各項目の

2つの場合が存在することができる次のような問題を呈する

通常ナップザック問題の

、最適な下部構造であります項目はソリューションに含まれていません。

したがって、nアイテムの最適解は、次の2つの値の最大値で与えられます。
1.最大値は、n-1アイテムとWです。
+ n-1の項目およびW-w_nの重量で得られる最大値。

n番目または(n-1)番目の項目がソリューションに存在する可能性があるという制約を追加すると、nの項目の最適解は、次の3つの値の最大値で与えられます。
1. n-2アイテムとWの重量で得られる最大値。
+ n-2の項目およびW-w_nの重量で得られる最大値。
+ n-2の項目およびW-w_(n-1)の重量で得られる最大値。

したがって、制約内の各要素のペアを1つの要素として扱い、O(Wn)時間で動的プログラミングアルゴリズムを実行します。