public class HouseColor {
private int [] colorcode;
public HouseColor(int [][] costMatrix)
{
colorcode = new int[costMatrix.length+1];
}
public int calcHouseColoringCost(int [][] M) {
int finalCost = 0;
int noOfHouses = M.length+1;
int noOfColors = M[0].length;
int [][] C = new int[noOfHouses][noOfColors];
int currHouseNoWithRespectToInputCostMatrix;
for (int i=0; i<noOfColors; i++) {
C[0][i] = 0;
}
for (int currHouseNo=1; currHouseNo < noOfHouses; currHouseNo ++) {
currHouseNoWithRespectToInputCostMatrix = currHouseNo - 1;
C[currHouseNo][0] = Math.min(C[currHouseNo-1][1], C[currHouseNo-1][2]) + M[currHouseNoWithRespectToInputCostMatrix][0];
C[currHouseNo][1] = Math.min(C[currHouseNo-1][2], C[currHouseNo-1][0]) + M[currHouseNoWithRespectToInputCostMatrix][1];
C[currHouseNo][2] = Math.min(C[currHouseNo-1][0], C[currHouseNo-1][1]) + M[currHouseNoWithRespectToInputCostMatrix][2];
colorCodeForCurrHouseNo(C[currHouseNo][0],C[currHouseNo][1],C[currHouseNo][2],currHouseNo);
}
//[1, 0, 2, 1, 0, 1]
//[5, 3, 4, 2, 1, 3]
//[1, 2, 2, 1, 0, 1] //wrong as two adjacent houses have same color
//[5, 1, 4, 2, 1, 3]
finalCost = Math.min(Math.min(C[noOfHouses - 1][0], C[noOfHouses - 1][1]), C[noOfHouses - 1][2]);
//printing the DP matrix.
System.out.println("Cost matrix leading to the solution: ");
printMatrix(C);
System.out.print("Color Code leading to the solution: ");
for(int i = 1 ;i<colorcode.length;i++)
{
System.out.print(colorcode[i]+" ");
}
System.out.println();
return finalCost;
}
public void colorCodeForCurrHouseNo(int a,int b,int c, int currHouseNo) {
int min = Math.min(Math.min(a, b), c);
int minColorCode = -1;
/*
System.out.println(a);
System.out.println(b);
System.out.println(c);
System.out.println(min);
System.out.println("-----XXXXX-----");
*/
if(min == a) minColorCode=0;
else if(min == b) minColorCode=1;
else if(min == c) minColorCode=2;
colorcode[currHouseNo] = minColorCode;
}
public void printMatrix(int [][]M) {
int noOfHouses = M.length;
int noOfColors = M[0].length;
for (int i=0; i < noOfHouses; i++) {
for (int j=0; j < noOfColors; j++) {
System.out.print(M[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int [][] costMatrix = {
{7, 5, 10},
{3, 6, 1},
{8, 7, 4},
{6, 2, 9},
{1, 4, 7},
{2, 3, 6},
};
HouseColor h = new HouseColor(costMatrix);
int cost = h.calcHouseColoringCost(costMatrix);
System.out.println("Cost of coloring the house is: " + cost);
}
}
There are a row of houses, each house can be painted with three colors red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?
Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.
Solution using dynamic programing.
The solution is as folows (calc(int, int) function):
1. If a best solution was found, use it.
2. Select one color not forbiden;
3. Solve the problem for n-1 houses.
4. get the best result adding best result for n-1 to current cost.
5. see if it is the current minimum when you add current color cost
6. update minimum if needed.
7. save best result.
Time complexity: Colors*Houses.
Space complexity: Colors*Houses.
Is easy to see it, if you realize that the runtime cost is the time to fill the best solution matrix, sized Colors*Houses.
By the way, for the problem stated above, the solution is:
Colors: [1, 0, 2, 1, 0, 1] (G, R, B, G, R, G)
Cost: 18
Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.
Solution using dynamic programing.
The solution is as folows (calc(int, int) function):
1. If a best solution was found, use it.
2. Select one color not forbiden;
3. Solve the problem for n-1 houses.
4. get the best result adding best result for n-1 to current cost.
5. see if it is the current minimum when you add current color cost
6. update minimum if needed.
7. save best result.
Time complexity: Colors*Houses.
Space complexity: Colors*Houses.
Is easy to see it, if you realize that the runtime cost is the time to fill the best solution matrix, sized Colors*Houses.
By the way, for the problem stated above, the solution is:
Colors: [1, 0, 2, 1, 0, 1] (G, R, B, G, R, G)
Cost: 18
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.