Programmation dynamique - Problème de variation de voleur

Question

J'ai rencontré un problème de programmation dynamique qui est une variation du voleur One.

Dites que vous êtes un voleur et que vous recevez un certain nombre de maisons de suite, vous devez voler:

$$ house_1, house_2 \ dots house_n $$

avec chaque maison ayant les valeurs suivantes: $$ (x_i \ geq y_i \ geq z_i \ gt0) $$

Vous profitez x si vous volez une maison mais aucune des maisons adjacentes .

Vous profitez y si vous volez une maison et exactement l'une des maisons adjacentes.

Vous profitez z si vous volez une maison et tous deux des maisons adjacentes .

étuis avec des maisons A-B-C serait:

$$ bénéfice (001)= 0 + 0 + c_x $$ $$ bénéfice (101)= a_x + 0 + c_x $$ $$ bénéfice (110)= a_y + b_y + 0 $$ $$ bénéfice (111)= A_Y + B_Z + C_Y $$

où 1 représente 1 robe la maison et 0 pour ne pas voler la maison

Évidemment, vous ne pouvez pas utiliser la valeur z pour la première et la dernière maison et chaque ensemble de valeurs est aléatoire.

La question est la suivante: quelles maisons devriez-vous voler pour obtenir le bénéfice maximum?

Mon problème principal est que je ne peux pas établir de cas de base pour ce problème.

Au début, j'ai pensé à créer un tableau N * M avec M étant la quantité maximale de maisons que je peux voler de 0-N lorsque chaque maison n'est pas volée et pensez comme: Rob It - Don 't Rob ça mais je suis arrivé avec rien.

Tous les conseils ou directions seraient appréciés.

Merci d'avance.

Answer 1

pour i= 1, \ points, n $ et $ r \ \ s, r, B \} $ définir $ opt [i, r] $ comme Le profit maximum pouvant être obtenu en volant un sous-ensemble approprié de la première $ i $ maisons avec les contraintes suivantes:

• si $ x= S $ (comme dans s kip) puis maison $ i $ ne doit pas être volé.
• si $ x= r $ alors house $ i $ doit être r OBbebed pendant la maison $ I + 1 $ ne sera pas volé (pour éviter une distinction de cas plus tard, nous prétendons que la maison $ I + 1 $ existe même lorsque $ I= N $ ).
• si $ x= b $ alors b house $ i $ et la maison $ i + 1 $ doit être volé.

pour $ i= 1 $ vous avez $ opt [1, s]= 0 $ , $ opt [1, r]= x_1 $ , $ opt [1, b]= y_1 $ .

pour $ i> 1 $ vous avez: $$ Opter [i, s]=max \ {opt [i-1, s], opte [i-1, r] \}, $$ $$ Opt [i, r]=max \ {x_i + opt [i-1, s], y_i + opt [i-1, b] \}, $$ $$ Opter [i, b]=max \ {y_i + opt [i-1, s], z_i + opt [i-1, b] \}. $$

Le profit optimal est alors: $ \ max \ {opt [n, s], opt [n, r] \} $ et peut être calculé dans $ O (n) $ temps globalement en utilisant les formules ci-dessus.