Optimization Problem with a Constraint

[FallenApple]

Homework Statement

This is a leetcode question.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Homework Equations

The constraint is two houses cannot be robbed.

The Attempt at a Solution

Actually, this is a solution I found online.

public int rob(int[] num) {
   if(num==null || num.length == 0)
       return 0;

   int even = 0;
   int odd = 0;

   for (int i = 0; i < num.length; i++) {
       if (i % 2 == 0) {
           even += num[i];
           even = even > odd ? even : odd;
       } else {
           odd += num[i];
           odd = even > odd ? even : odd;
       }
   }

   return even > odd ? even : odd;
}

The code is in Java. I'm not sure why the even and odd "pointers" need to switch. How does this solve the problem? We know they cannot rob two houses in a row. But how does this relate to evens and odds? If what is considered even and odd constantly switches, then what is the purpose of giving them the names in the first place?

 

[andrewkirk]

They don't switch. At each step, which corresponds to the next house in the row and wondering whether to rob it, there are always two totals, named odd and even. At house i, the odd (even) total is the biggest amount that can be obtained from robbing some collection of houses up to and possibly including the biggest odd (even) number <= i. Sometimes those two totals are the same, which is what comes out of the expressions 'even > odd ? even : odd'.

The difference between the even and odd totals is that, if i is odd (even), the odd (even) total encompasses the possibility (but not the necessity) of robbing house i, while the even (odd) total does not.

Consider the sequence of stashed sums 5 3 2.

At i=1, we have even=0, odd=5, because the odd pattern can rob house 1 but the even pattern can rob no houses.
At i=2, the even pattern could rob house 2 to get $3, but it is better to rob house 1 instead, as that nets a bigger amount and yet leaves open the possibility of robbing house 3 next, which robbing house 2 doesn't.

Now consider the pattern of stashed sums 3 5 7 2

At i = 1 we have even=0, odd=3
At i = 2 we have even=5, odd=3 because 5>3
At i = 3 we have even=5, odd=10 because 10>5
At i=4 we have even=10, odd=10 because robbing house 4 together with the existing even strategy nets a total of only 5+2=7, which is less than the 10 obtained from the odd strategy.

It's a neat solution.

 

[donpacino]

The only problem I have with this solution...

You'd think an additional constraint would be added limiting the number of houses one can rob per night. This solution assumes if you have 800 houses on the block you can rob half of them. It also assumes houses are only on one side of the street. Its possible that those assumptions are correct, but it seems too easy.

 

[donpacino]

It also fails for certain patterns. In the following pattern you would be better off going with house 2, 4, 7 then 2,4,6,8

1 20 1 20 1 1 20 1

 

[andrewkirk]

It also fails for certain patterns. In the following pattern you would be better off going with house 2, 4, 7 then 2,4,6,8

1 20 1 20 1 1 20 1

The algorithm does choose 2 4 7 for that pattern. Here's the sequence:

Step; Odd Sequence; Even Sequence
1; 1; none
2; 1; 2
3; 2; 2
4; 2; 2 4
5; 2 4; 2 4
6; 2 4; 2 4 6
7; 2 4 7; 2 4 6
8; 2 4 7; 2 4 7

 

[donpacino]

ahhh true. For some reason I interpreted the code as a convoluted way to sum up the odd and even numbers