Programação dinâmica - problema de variação do ladrão

Question

Eu encontrei um problema de programação dinâmica que é uma variação do ladrão um.

Diga que você é um ladrão e você recebe uma série de casas em uma linha que você deve roubar:

$$ house_1, house_2 \ dots house_n $$

Com cada casa tendo os seguintes valores: $$ (x_i \ geq y_i \ geq z_i \ gt0) $$

você lucra x se você roubar uma casa, mas nenhuma das casas adjacentes .

você lucra y se você roubar uma casa e exatamente uma das casas adjacentes .

Seu lucro z se você roubar uma casa e ambas as casas adjacentes .

casos com casas A-B-C seria:

$$ lucro (001)= 0 + 0 + c_x $$ $$ lucro (101)= A_X + 0 + C_X $$ $$ lucro (110)= a_y + b_y + 0 $$ $$ Lucro (111)= A_Y + B_Z + C_Y $$

onde 1 representa roubando a casa e 0 para não roubar a casa

Obviamente você não pode utilizar o valor z para a primeira e a última casa e cada conjunto de valores é aleatório.

Agora a questão é: quais casas você deve roubar para obter o máximo lucro?

Minha principal questão é que não consigo estabelecer uma caixa de base para este problema.

A princípio, pensei em criar uma matriz n * m com m sendo a quantidade máxima de casas que posso roubar de 0-n quando cada casa não é roubada e pense como: Rob It - Don Não roubá, mas não apareceu nada.

Qualquer dicas ou direções seria apreciada.

Agradecemos antecipadamente.

Answer 1

para $ i= 1, \ pontos, n $ e $ r \ in \ {s, r, B} $ Definir $ opt [i, r] $ como O lucro máximo que pode ser obtido roubando um subconjunto adequado da primeira $ i $ casas com as seguintes restrições:

• se $ x= S $ (como em s kip), então abriga $ i $ não deve ser roubado.
• se $ x= R $ então casa $ i $ deve ser r obbed enquanto casa $ i + 1 $ não será roubado (para evitar uma distinção do caso depois, fingimos que a casa $ i + 1 $ existe mesmo quando $ i= n $ ).
• se $ x= B $ então b a casa $ i $ e casa $ i + 1 $ precisa ser roubado.

para $ i= 1 $ você tem $ opt [1, s]= 0 $ , $ opt [1, r]= x_1 $ , $ opt [1, b]= y_1 $ .

para $ i> 1 $ você tem: $$ 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] \}. $$

O lucro ideal é então: $ \ max \ {opt [n, s], opt [n, r] \} $ e pode ser calculado em $ O (n) $ tempo geral usando as fórmulas acima.