Good solution buddy, thanks for the answer.
On 26 December 2013 17:25, Saurabh Paliwal <[email protected]>wrote: > @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]. > -- 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].
