未加星标

House painting problem

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二05 | 时间 2017 | 作者 红领巾 ] 0人收藏点击收藏
The question

There are a row of houses, each house can be painted with one of three colors red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?

Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.

The solution

There is a trivial solution to this problem, which would be to calculate all the possible combinations and then choose the one with the lowest cost. If we had only two houses we could calculate: red-green, red-blue, green-red, green-blue, blue-red, blue-green; a total of 6 combinations. Things start getting more complicated pretty fast. With three houses:

red-green-red

red-green-blue

red-blue-red

red-blue-green

green-red-green

green-red-blue

green-blue-green

green-blue-red

blue-red-blue

blue-red-green

blue-green-blue

blue-green-red

This time we have 12 combinations, which is twice as much as with 2 houses. If we had 4 houses we would have 24 combinations. It could seem like the complexity is N*2 where N is the number of houses, but it only increases by 2 because we have 3 colors. If we added one more color, we would have the following combinations for 2 houses:

red-green

red-blue

red-yellow

green-red

green-blue

green-yellow

blue-red

blue-green

blue-yellow

yellow-red

yellow-green

yellow-blue

This time we have 12 combinations for 2 houses with 4 different colors. If we added one more house we would end up with 36 combinations.

In both cases, adding one house results on: (new number of combinations) = (previous number of combinations) * (M 1), where M is the number of colors. Taking into account that for the scenario of one house we can actually use M instead of M-1, we can model our complexity as: M * ((M-1)^(N-1)). In a simplified O notation you would probably say it’s O(M^N)

This complexity is pretty bad and can in most cases be optimized by using other techniques. In general for these kind of problems we need to find patterns and invariants. We have already found the number of possible combinations, which is a good start but now we need to find ways to reduce the number of combinations.

A technique I like to follow when facing these problems is to start very small. Using a single color is not possible because you can’t have two houses painted the same color together. Using two colors is also not very useful because there are only two possibilities no matter how many houses there are. If the colors are reg and green, you either start with red or start with green and then interpolate the colors until there are no more houses.

The problem starts taking form when there are 3 colors, so lets start from there. If we had 1 house, we just pick the cheapest color. If we had 2 houses, it is also pretty simple, we check all the combinations and pick the cheapest one. Adding one more house starts making things more interesting. Here is where we want to start looking for shortcuts. We already know that calculating all combinations and taking the cheapest would work, but we are trying to find a better way.

There is actually a little invariant hidden in this problem that can be observed when dealing with 3 houses. We can paint the last house one of 3 colors red, green or blue. This is information we can’t change. The way we decide which color to paint it is based on information about all the previous houses. Another invariant is that if we painted the last house red, we can only paint the previous house green or blue. But how do we choose which color is best?

We decided we want the last house to be red, this means the second house can only be green or blue. Lets assume that we calculated all combinations for 2 houses and found that if you had to choose between painting the second house green or blue, the cheapest combination ends with a green house. At this point, you don’t care about the combination x-blue-red because you already know that x-green-red is cheaper. You can follow the same process assuming you decide to paint the third house green or blue.

Then you end with the cheapest price for painting the last house on each of the three colors. If you add one more house you just need these 3 values to figure out which color to paint it. You can keep adding houses and the process will remain the same.

Using this technique we have reduced the complexity to N * M. For each of the houses you have to calculate the price for each of the colors.

Now that we know the algorithm we can write the code for it:

// An array containing the costs of painting each // house in a given color var costs = [ { r: 4, g: 20, b: 3 }, { r: 10, g: 4, b: 6 }, { r: 33, g: 10, b: 7 }, { r: 90, g: 85, b: 89 }, { r: 1, g: 9, b: 1 } ]; var n = costs.length; // number of houses var c = 3; // number of colors function solve() { var lowest = []; lowest.push({ r: costs[0].r, g: costs[0].g, b: costs[0].b }); for (var h = 1; h

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

分页:12
转载请注明
本文标题:House painting problem
本站链接:http://www.codesec.net/view/531326.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(24)