Tuesday, 19 January 2016

Maximize the robbery

A robber enters a colony of houses numbered from 1 to n.  Every house has a number printed on the top of it. That number is the amount of money inside that house. However, there is one constraint. If the robber cannot robs from money from consecutive houses. How can the robber maximize his robbery?

Solution:
If Robber robs from i-th house, he can't rob house no i-1 and house no i+1.

Dynamic Programming logic:

dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);

Implementation in Java:

import java.util.Scanner;
public class MaximiseRobbery {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int houses = scan.nextInt();
int[] amPerHouse = new int[houses];
for (int i = 0; i < houses; i++) {
amPerHouse[i] = scan.nextInt();
}
int maximumRobbery = maximizeRobbery(amPerHouse, houses);
System.out.println(maximumRobbery);
scan.close();
}

/**
* Method to maximise the robbery
* @param amPerHouse
*/
private static int maximizeRobbery(int[] amPerHouse,int houses) {
if (houses == 1) {
return amPerHouse[0];
} else if (houses == 2) {
return Math.max(amPerHouse[0], amPerHouse[1]);
}
int[] dp = new int[amPerHouse.length];
dp[0] = amPerHouse[0];
dp[1] = amPerHouse[1];
for (int i = 2; i < houses; i++) {
dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);
}
return dp[houses - 1];
}
}

Reference: