@atul anand :- no, we need not use all the colors.
@kumar raja :- sorry dude for replying this late. Continuing with the
previous idea, I extend the solution for the modified problem as
1. let answer[i][j][0] represent minimum cost of coloring i houses when ith
house is colored with jth color and so is the (i-1)th house.
2. let answer[i][j][1] represent minimum cost of coloring i houses when ith
house is colored with jth color and (i-1)th is not.
The recurrence will be
3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]*
4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) +
colorvalue[j]* for all t from 1 to k except j.
// In the first problem, I mistakenly wrote colorvalue[t] here. It will be
colorvalue[j] there. ( sorry for the confusion )
5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all j
from 1 to k.
6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j].
Also now that I read the problem, I guess colorvalue is not fixed for every
color, so that will be a 2-D matrix as well.
*replace every colorvalue[j] with colorvalue[i][j] in the above recurrences*.
( i is the house number, j is the color number )
On Wed, Dec 18, 2013 at 10:16 PM, atul anand <atul.87fri...@gmail.com>wrote:
> @kumar : i have one doubt regarding this question.Do we have to use all K
> colors[K] to color all building.
>
> for example :-
>
> color[3]={1,2,10};
>
> now if we have to color 6 building then i can use only 1st 2 color to
> color all building and never 10 ...is this allowed ???
> building[N]={1,2,1,2,1,2}
>
>
> On Sun, Dec 15, 2013 at 12:44 AM, kumar raja <rajkumar.cs...@gmail.com>wrote:
>
>> You have 'n' houses and 'k' colors. The cost of coloring a house with one
>> of the 'k' colors is different from coloring another house with same color.
>> The cost of coloring the house with different colors are different. So now
>> how to colour the 'n' houses such that no two adjcent houses will get the
>> same color and the total coloring cost for 'n' houses is minimized.
>>
>>
>>
>> Regards,
>> Kumar Raja.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
- Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
