GATE CSE
First time here? Checkout the FAQ!
x
0 votes
103 views
In a village, people build houses in the same side of the road. A thief plans to loot the village. He wants maximum amount of money without having any risk of getting caught. By some means, the villagers know that their adjacent house is being looted or not and thus they become alert. So the thief cannot loot contiguous two houses. Given that the thief knows the amount of money stored in each house and the road is straight and there is no turning, which is the most efficient algorithmic strategy to solve this problem?

(a) Brute force

(b) Dynamic programming

(c) Backtracking

(d) Divide and conquer

 

Please provide explanation to your solution :)
asked in Algorithms by Junior (883 points)   | 103 views
bruteforce...

1 Answer

0 votes

Brute force - This method most inefficient of all as there is more possibilty for the robber to get caught. So, we can eliminate this.

Divide and Conquer - He can only visit some of the houses and not all. So we can eliminate this.

Dynamic programming - This is better than above two but while identifying subproblem,he would decide to rob alternate houses(He wouldn't get caught). But by doing so he wont be able to get maximum profit. This is good algorithm because he can start from house where highest amount of money is stored.

Backtracking - The robber can rob at alternate houses and at the end of street he can backtrack all the way back to start of the street and again start robbing the houses he had skipped in the first round. By doing this way he might steal all the houses in street. But this doesn't always happen always, backtracking would select any one of the choices currently available if it provides the solution then it continues else it backtracks and chooses another choice. Given the circumtances, robber cannot do trails(he might get caught).

So, Option B

answered by Active (1.2k points)  
edited by
but ans given is (b)
Yeah right, backtracking starts with any one of the possible moves currently available not always the way I had described.But if backtracking always follows the moves in the way I described then it would have been best algorithm, unfortunately it doesn't. I'll edit the answer. Why didn't I think this?


Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users