@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 <[email protected]>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 <[email protected]>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 [email protected]. >> > > -- > 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 [email protected]. > -- - 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 [email protected].
