各種リュック6(グループバック問題)

各種リュック6(グループバック問題)
に質問
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.これらのアイテムはいくつかのグループに分けられ、各グループのアイテムは互いに衝突し、最大1つを選択します.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
アルゴリズム#アルゴリズム#
この問題は、各グループのアイテムにはいくつかの戦略があります.このグループのいずれかを選択するか、それとも1つも選択しないかです.すなわち、f[k][v]が前k組の物品費費用vが取得できる最大の権利値を示すとすると、f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]| i k}
1 D配列を使用する疑似コードは次のとおりです.

for     k
for v=V..0
for    i   k
f[v]=max{f[v],f[v-c[i]]+w[i]}

ここの3層ループの順序に注意して、本文の最初のbeta版の中で私自身も書き間違えました.「for v=V..0」というレイヤループは、「forのすべてのiがグループkに属する」以外でなければならない.これにより、各グループ内のアイテムがリュックサックに追加されるのは最大1つだけであることが保証されます.
さらに,各グループ内の物品に完全リュックサック問題における「単純で効率的な最適化」を適用できることは明らかである.
小結
グループ化されたリュックサック問題は、互いに反発するいくつかのものをグループと呼び、良いモデルを構築した.多くのリュックサック問題の変形はグループ化されたリュックサック問題(例えば依存するリュックサック問題)に転化することができ、グループ化されたリュックサック問題からさらに「汎化物」の概念を定義することができ、問題を解くのに非常に有利である.code:
for
 (
int
 i
=
0
; i
<=
V; i
++
) s[i]
=
0
;
for
 (
int
 i
=
1
; i
<=
M; i
++
){      
for
 (
int
 j
=
V; j
>=
0
; j
--
)      {            
for
 (
int
 k
=
1
; k
<=
N; k
++
)            {                  
if
 (
set
[k]
==
i)                  {                        
if
 (j
<
v[k]) 
continue
;                        s[j]
=
max(s[j], s[j
-
v[k]]
+
w[k]);                  }            }      }}