retagged by
2,371 views
0 votes
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 :)
retagged by

1 Answer

0 votes
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

edited by
Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Mar 31, 2020
8,491 views
The Knapsack problem belongs to which domain of problems?OptimizationNP completeLinear SolutionSorting
0 votes
0 votes
1 answer
2
go_editor asked Mar 27, 2020
2,318 views
Binary search tree is an example of :Divide and conquer techniqueGreedy algorithmBack trackingDynamic Programming
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Jun 26, 2019
209 views
Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta (n\ lg\ n)$ worst-case time. (Hint: Modify merge sort.)
0 votes
0 votes
1 answer
4
akash.dinkar12 asked Jun 26, 2019
360 views
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whos...