Dynamische Programmierung - Dieb-Variationsproblem

Question

Ich habe ein dynamisches Programmierproblem begegnet, das eine Variation des Diebs eins ist.

Sagen Sie, Sie sind ein Dieb, und Sie erhalten eine Reihe von Häusern in einer Reihe, die Sie rauben sollten:

$$ house_1, house_2 \ dots house_n $$

Mit jedem Haus mit den folgenden Werten: $$ (x_i \ geq y_i \ geq z_i \ gt0) $$

Sie profitieren x wenn Sie ein Haus rauben, aber keiner der angrenzenden

Sie profitieren y wenn Sie ein Haus rauben und genau eines der angrenzenden Häuser.

Sie profitieren z wenn Sie ein Haus rauben und beide der angrenzenden Häuser.

Fälle mit Häusern A-B-C wäre:

$$ Gewinn (001)= 0 + 0 + c_x $$ $$ Gewinn (101)= A_X + 0 + C_X $$ $$ Gewinn (110)= A_Y + B_Y + 0 $$ $$ Gewinn (111)= A_Y + B_Z + C_Y $$

wo 1 steht, um das Haus zu rauben und 0, um das Haus nicht auszuberufschen

Natürlich können Sie den z -wert für das erste und das letzte Haus nicht nutzen, und jeder Satz von Werten ist zufällig.

Jetzt ist die Frage: Welche Häuser sollten Sie rauben, um den maximalen Gewinn zu erhalten?

Mein Hauptproblem ist, dass ich keinen Grundfall für dieses Problem aufbauen kann.

Ich dachte zunächst daran, ein n * m-Array mit m zu erstellen 'Ich rieb es aber nichts.

Alle Tipps oder Richtungen würden geschätzt.

Vielen Dank im Voraus.

Answer 1

für $ i= 1, \ dots, n $ , und $ r \ in \ {s, r, B \} $ Definieren Sie $ opt [i, r] $ als Der maximale Gewinn, der erhalten werden kann, indem Sie eine geeignete Teilmenge des ersten Häuser von $ I $ mit den folgenden Einschränkungen ausräumen:

.
• wenn $ x= s $ (wie in s kip), dann Haus $ i $ darf nicht ausgeraubt werden.
• wenn $ x= r $ dann haus $ i $ muss r Obbed während Haus $ i + 1 $ wird nicht ausgeraubt (um ein Fall zu vermeiden, dass wir später vorgeben, dieses Haus $ i + 1 $ existiert, auch wenn $ i= n $ ).
• wenn $ x= B $ dann b oth house $ i $ und Haus $ i + 1 $ müssen ausgeraubt werden.

für $ i= 1 $ Sie haben $ opt [1, s]= 0 $ , $ opt [1, r]= x_1 $ , $ opt [1, b]= y_1 $ .

für $ i> 1 $ Sie haben: $$ Opt [i, s]=max \ {opt [i-1, s], opt [i-1, r] \}, $$ $$ Opt [i, r]=max \ {x_i + opt [i-1, s], y_i + opt [i-1, b] \}, $$ $$ Opt [i, b]=max \ {y_i + opt [i-1, s], z_i + opt [i-1, b] \}. $$

Der optimale Gewinn ist dann: $ \ max \ {opt [n, s], opt [n, r] \} $ und kann in berechnet werden $ O (n) $ Gesamtzeit mit den obigen Formeln.