The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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 :)

(a) Brute force

(b) Dynamic programming

(c) Backtracking

(d) Divide and conquer

Please provide explanation to your solution :)

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**

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,156 questions

36,980 answers

92,147 comments

34,822 users