2

私はこの演習を解決しようとしています: n 個のアイテムが与えられ、それぞれが指定された非負の重量 w1,w2,...,wn と値 v1,v2,...,vn と、最大重量容量のナップザックを持っていますW. 最大値のサブセット S を見つける必要がありますが、次の 2 つの制限があります。1) セットの総重量は W を超えてはなりません。2) 連続したインデックスを持つオブジェクトを取得できません。

たとえば、n = 10 の場合、考えられる解は {1, 4, 6, 9}、{2, 4, 10} または {1, 10} です。

正しい繰り返しを作成するにはどうすればよいですか?

4

1 に答える 1

5

DP ソリューションに使用されるナップザック再帰式が次のとおりであることを思い出してください。

D(i,w) = max { D(i-1,w) , D(i-1,w-weight[i]) + value[i] }

変更された問題で、取ることを選択した場合i- を取ることができずi-1、次の変更が生じます。

D(i,w) = max { D(i-1,w) , D(i-2,w-weight[i]) + value[i] }
                              ^
                          note here 
                       i-2 instead of i-1

従来のナップサックと同様に、これも徹底的な検索であり、同じ理由で最適なソリューションを提供します。
選択することを決定したという考えが与えられます。選択iすることはできませんi-1。そのため、多くてもアイテムを使用する最適なソリューションを見つけてi-2ください。(除外することにした場合、元からの変更はありませんi)

于 2013-01-10T10:50:39.230 に答える