4
$\begingroup$

I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be either positive or negative value. But the aim is to maximize the profit by buying a subset of these houses. So infact, you should buy houses which are >0 value. However, you cannot buy houses that adjacent to the house you are buying, e.g i-1 and i+1 should not be bought. I am not quite sure where to start to look at this problem, I mean what exactly will be the difference of looking it from the greedy or dynamic programing way. Thanks for any suggestion.

$\endgroup$
  • 3
    $\begingroup$ Will the greedy algorithm work if the houses have profit (2,4,3) in that order? $\endgroup$ – Peter Shor Oct 25 '12 at 0:29
  • $\begingroup$ The greedy algorithm will not work because it will aim for 4, which is the highest one, and then drop the ones besides it. $\endgroup$ – user1675999 Oct 25 '12 at 23:00
5
$\begingroup$

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

Update:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $[h_i \ldots h_j]$ for $1\leq i < j\leq n$,

$\endgroup$
  • $\begingroup$ Thanks, I think that helps. I was actually stuck with the knapsack problem. One pattern I see is that does it have to have a two dimensional array like the way the knapsack problem was solved. To me, I think using a one dimensional array to store the previous profit values is also feasible?. Any suggestion, Thank you $\endgroup$ – user1675999 Oct 25 '12 at 22:58
  • $\begingroup$ Yes, you should be able to make do with a 1D array. $\endgroup$ – PKG Oct 25 '12 at 23:05
  • $\begingroup$ ohkay so i got the equation but idk if it's correct, like you know how in knapsack problem, you can see the point where the value starts changing is the one that you pick, e.g if you have the solution to profit as in the array as 4,4,4,6,8... for the houses with in the ascending order, with values 4,2,-6,2,4 $\endgroup$ – user1675999 Oct 25 '12 at 23:58

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.