package test;
import java.util.Arrays;
public class PaintHouse
{
private int[][] cost;
private BestResult[][] best;
private int totalColors;
private int totalHouses;
public class BestResult
{
public int[] colors;
public int cost;
public BestResult(int[] colors, int cost)
{
this.colors = colors;
this.cost = cost;
}
}
public PaintHouse(int[][] cost)
{
this.cost = cost;
this.totalColors = cost.length;
this.totalHouses = cost[0].length;
this.best = new BestResult[totalColors][totalHouses];
}
public BestResult calc()
{
return calc(totalHouses, -1);
}
private BestResult calc(int totalHouses, int forbiddenColor)
{
System.out.println("-------------------XXXXXX-------------------");
// If a best solution was found, use it.
if (forbiddenColor >= 0 && best[forbiddenColor][totalHouses - 1] != null)
{
System.out.println("best solution was found , so returning from best matrix ");
return best[forbiddenColor][totalHouses - 1];
}
// If a best solution was not found.
System.out.println("best solution was not found , so entering the for loop to calculate it ");
BestResult min = null;
System.out.println("forbiddenColor : "+forbiddenColor);
for (int color = 0, house = cost[0].length - totalHouses; color < totalColors; ++color)
{
System.out.println("inside for : color -> " +color+" , house -> "+house);
int currentCost = cost[color][house];
// Select one color not forbidden
if (color != forbiddenColor)
{
System.out.println("current color is not forbidden");
if (totalHouses == 1)
{
System.out.println("totalHouses are 1");
if (min == null || min.cost > currentCost)
{
min = new BestResult(new int[] { color }, currentCost);
}
} // end of inner if
else
{
System.out.println("totalHouses are > 1");
// Solve the problem for n-1 houses
System.out.println("Solve the problem for n-1 houses");
BestResult next = calc(totalHouses - 1, color);
System.out.println("Back from recursive call");
System.out.println("-------------------XXXXXX-------------------");
// get the best result adding best result for n-1 to
// current cost
currentCost = currentCost + next.cost;
// 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] = color;
/*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 (forbiddenColor >= 0)
{
best[forbiddenColor][totalHouses - 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.