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.
$\begingroup$
$\endgroup$
2
asked Oct 25, 2012 at 0:06
-
3$\begingroup$ Will the greedy algorithm work if the houses have profit (2,4,3) in that order? $\endgroup$– Peter ShorCommented Oct 25, 2012 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$– user1675999Commented Oct 25, 2012 at 23:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$,
-
$\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$ Commented Oct 25, 2012 at 22:58
-
$\begingroup$ Yes, you should be able to make do with a 1D array. $\endgroup$– PKGCommented Oct 25, 2012 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$ Commented Oct 25, 2012 at 23:58