The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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 Active (1.1k points) | 128 views

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.5k 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?

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,156 questions
36,980 answers
34,822 users