Minimum cost for colouring the house?

935 Views Asked by At

I came across below problem

There are N houses in a row. Each house can be painted in either Red, Green or Blue color. The cost of colouring each house in each of the colours is different. Find the colour of each house such that no two adjacent houses have the same colour and the total cost of colouring all the houses is minimum.

Here is the complete question

The problem to me looks bit confusing, as objective is to minmize the cost and ensure that no adjacent house have same colour. In that case should not i select the just two colours out of three whose cost is minimum.

Say here is the cost of colours

  1. Red $100
  2. Green $200
  3. Blue $300

I have 5 row houses to paint

Here will be my Algo

  1. Select Red and Green colour as their cost is minimum
  2. calculate 5%2.

    If 5%2 == 1 then start from last and select the colour of last house as Red($100). Now choose the alternate colour

    If 5%2 == 0 then start from beginning and choose the alternate colour

I see Is "house coloring with three colors" NP? suggested the dynamic programming But i am not sure what is wrong with my approach and why dynamic programming is required here ?

1

There are 1 best solutions below

1
On

This is (presumably) a homework problem. I think the intention is to teach you to implement a greedy algorithm:

  1. Paint the first house using the cheapest color ("red").
  2. Paint the next house using the cheapest color available.

The second will alternate between "red" and "green", but you don't have to choose the colors in advance.

If I were assigning this problem, the next problem would be "And solve this assuming you have only enough paint for one red house".