Minimum cost for colouring the house?

0
votes

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
algorithmlanguage-agnosticdynamic-programming
Probably the author intended a cost for each house-color combination, so that you can't statically choose your colors. Otherwise, that's a reasonable idea. – David Eisenstat
@DavidEisenstat here main intention is no two adjacent houses have the same colour and the total cost of colouring all the houses is minimum. so even if author intended a cost for each house-color combination, minimum cost will be what i explained in my algo. Here is the full question careercup.com/question?id=9941005 – user3198603
There's a clarification there that painting house 1 red does not always cost the same as painting house 2 red. – David Eisenstat
And in general, you need all of the colors, e.g., if there are three houses, and #1's cheapest is red, #2's cheapest is green, and #3's cheapest is blue. – David Eisenstat

1 Answers

0
votes

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".