import java.util.*;
import java.lang.*;
import java.io.*;
public class BestResult {
public int[] colors;
public int cost;
public BestResult(int[] colors, int cost)
{
this.colors = colors;
this.cost = cost;
}
}
public class PaintHouse
{
private int[][] cost;
private BestResult[][] best;
private int noOfHouses;
private int noOfColors;
public PaintHouse(int[][] cost)
{
this.cost = cost;
this.noOfColors = cost.length;
this.noOfHouses = cost[0].length;
this.best = new BestResult[noOfColors][noOfHouses];
}
public BestResult calc()
{
return calc(noOfHouses, -1);
}
private BestResult calc(int noOfHouses, int forbiden)
{
//If a best solution was found, use it.
if (forbiden >= 0 && best[forbiden][noOfHouses - 1] != null)
return best[forbiden][noOfHouses - 1];
BestResult min = null;
for (int c = 0, h = cost[0].length - noOfHouses; c < noOfColors; ++c)
{
//Select one color not forbiden
if (c != forbiden)
{
if (noOfHouses == 1)
{
if (min == null || min.cost > cost[c][h])
{
min = new BestResult(new int[] {c}, cost[c][h]);
}
}// end of inner if
else
{
//Solve the problem for n-1 houses
BestResult next = calc(noOfHouses - 1, c);
//get the best result adding best result for n-1 to current cost
int currentCost = next.cost + cost[c][h];
//see if it is the current minimum when you add current color cost
if (min == null || min.cost > currentCost)
{
//update minimum if needed
min = new BestResult(new int[next.colors.length + 1],currentCost);
min.colors[0] = c;
// arraycopy(Object src, int srcPos, Object dest, int destPos, int lengthOfSource)
System.arraycopy(next.colors, 0,min.colors, 1, next.colors.length);
}// end of if inside inner else
} //end of inner else
} //end of outer if
} //end of for loop
if (forbiden >= 0) best[forbiden][noOfHouses - 1] = min;
return min;
}//end of calc
public static void main(String [] args)
{
int[][] cost = new int[][] {
new int[] { 7, 3, 8, 6, 1, 2},
new int[] { 5, 6, 7, 2, 4, 3},
new int[] {10, 1, 4, 9, 7, 6}
};
PaintHouse p = new PaintHouse(cost);
BestResult bestResult = p.calc();
System.out.println("Colors: " + Arrays.toString(bestResult.colors));
System.out.println("Cost: " + bestResult.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.