3
$\begingroup$

I've encountered a Dynamic Programming problem which is a variation of the thief one.

Say you are a thief and you are given a number of houses in a row you should rob :

$$House_1,House_2 \dots House_N$$

with each house having the following values : $$(x_i \geq y_i \geq z_i \gt0)$$

You profit X if you rob a house but none of the adjacent houses.

You profit Y if you rob a house and exactly one of the adjacent houses.

You profit Z if you rob a house and both of the adjacent houses.

Cases with houses A-B-C would be :

$$Profit(001)=0+0+C_x$$ $$Profit(101)=A_x+0+C_x$$ $$Profit(110)=A_y+B_y+0$$ $$Profit(111)=A_y+B_z+C_y$$

Where 1 stands for robbing the house and 0 for not robbing the house

Obviously you can't utilize the Z value for the first and the last house and each set of values is random.

Now the question is : Which houses should you rob to get the maximum profit?

My main issue is that i can't establish a base case for this problem.

At first i thought of creating a N*M array with M being the maximum amount of houses i can rob from 0-N when every house is not robbed and think like : Rob it - Don't rob it but came up with nothing.

Any tips or directions would be appreciated.

Thanks in advance.

$\endgroup$
4
$\begingroup$

For $i=1,\dots,N$, and $r \in \{S,R,B\}$ define $OPT[i,r]$ as the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints:

  • If $x=S$ (as in Skip) then house $i$ must not be robbed.
  • If $x=R$ then house $i$ must be Robbed while house $i+1$ will not be robbed (to avoid a case distinction later we pretend that house $i+1$ exists even when $i=N$).
  • If $x=B$ then Both house $i$ and house $i+1$ need to be robbed.

For $i=1$ you have $OPT[1,S] = 0$, $OPT[1,R] = x_1$, $OPT[1,B] = y_1$.

For $i>1$ you have: $$ 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] \}. $$

The optimal profit is then: $\max\{OPT[N, S], OPT[N, R] \}$ and can be computed in $O(N)$ overall time using the above formulas.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.