2

私はKnapsack ProblemDPの古典を理解しているので、（無制限の）について読んでいます。
読んでいるうちに解決策は理解できたと思いますが、実際のコードに変換する方法がわかりません。
たとえば、次の漸化式「式」では、次のようになります。

M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1

これをコードに変換する方法がわかりません。内部MAXがそこにあるべきか、代わりにあるべきかが明確ではないためです。
M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1

数式を理解してコーディングするのに役立つものはありますか？

4

1 に答える 1

7

次のようにコーディングできます。

for w = 0 to W   //W is the maximum capacity
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 0 to W
    if wi <= w // item i can be part of the solution
        if  bi + V[i-1,w-wi] > V[i-1,w]
            V[i,w] = bi + V[i-1,w- wi]
        else
            V[i,w] = V[i-1,w]
    else V[i,w] = V[i-1,w]  // wi > w

ここに画像の説明を入力してください

これは次のことを意味します。

つまり、総重みwを持つSkの最良のサブセットは次のとおりです。

1）総重量がwより大きいSk-1の最良のサブセット、または

2）総重量>w-wkとアイテムkを持つSk-1の最良のサブセット

総重み>wを持つSkの最良のサブセットは、アイテムkを含むか含まないかのいずれかです。

最初のケース：wk>w。アイテムkをソリューションに含めることはできません。そうすると、総重量が> wになり、許容できないためです。

2番目のケース：wk<=w。次に、項目kを解に含めることができ、より価値の高いケースを選択します。

于 2012-12-31T16:28:59.830 に答える