动态规划proboem最低成本 [英] dynamic programming proboem for minimum cost

问题描述

我有一个手机信号塔的问题。有n个乡镇。我们希望在一些乡镇建立手机信号塔。每个单元塔可覆盖本身和它的邻居。每个镇有一个成本打造的手机信号塔。我们要找出建立手机信号塔覆盖所有乡镇的最低成本。

I have a cell tower question. There are n towns. We want to build cell tower in some of the towns. Each cell tower can cover itself and its neighbor. Each town has a cost to build cell tower. We want to find out the minimum cost to build the cell tower to cover all towns.

例如，

（1）

COST 5 1 2 我们选择在城里-2打造的手机信号塔。成本是1。

COST 5 1 2 We select to build cell tower in town-2. The cost is 1.

（2）

COST 5 1 2 3 我们选择在城里-2/3打造的手机信号塔。的成本是1 + 2 = 3

COST 5 1 2 3 We select to build cell tower in town-2/3. The cost is 1+2=3.

（3）

COST 5 1 3 2

COST 5 1 3 2

我们选择在城里-2/4，以建立手机信号塔。的成本是1 + 2 = 3

We select to build cell tower in town-2/4. The cost is 1+2=3.

这是一个动态规划算法。我该如何解决呢？

It's a dynamic programming algorithm. How can I solve it?

谢谢 凌

推荐答案

我的东西去以下行中：

f(0,_) = 0
f(1,true) = 0
f(1,false) = cost[1]
f(x,true) = min{ f(x-1,true) + cost[x], f(x-1,false) }
f(x,false) = min { f(x-1,true) + cost[x], f(x-2,true) + cost[x-1]}

我们的想法是：

The idea is:

X 是城市的当前数量，我们正在研究，并布尔是真实的，如果这个城市已经覆盖（增城市从左边）。

x is the current number of city we are looking at, and the boolean is true if this city is already covered (by the city from the left).

• F（0，_）是一个空基地条款 - 它是免费的覆盖没有
• F（假）为基地，全市1不是盖的，所以你必须把塔那里， F（1，真）是城市1涵盖了基础，所以你并不需要一个塔，和你做。
• F（X，真）是这样的X城市已经覆盖，所以你可以把有一座塔，并持续到下一个城市[这是还包括 - F（X-1，真）]，或不把塔那里，下一个城市不是盖的[ F （X-1，FALSE）]
• F（X，FALSE）是X城市不是盖的，所以你基本上有两种选择，或者放一个塔在那里，然后再继续的情况下 F（X-1，真）。或者放一个塔，在未来的城市（在X-1），然后继续 F（X-2，真）

• f(0,_) is an empty base clause - it is free to cover nothing.
• f(1,false) is base where city 1 is not covered, so you must put a tower there, and f(1,true) is a base where city 1 is covered, so you don't need a tower and you are done.
• f(x,true) is the case that the city x is already covered, so you can put there a tower, and continue to the next city [which is also covered - f(x-1,true)], or don't put a tower there, and the next city is not covered [f(x-1,false)]
• f(x,false) is the case where city x is not covered, so you basically have two choices, or put a tower in there, and then continue to f(x-1,true). Or put a tower in the next city (in x-1) and then continue to f(x-2,true)

开始用 F（X，FALSE），其中 X 是最后一个城市，你会得到最小的解决方案。
是容易看出，这个递推公式可以很容易地修改，以DP。

Start with f(x,false), where x is the last city, and you'll get the minimal solution.
It is easy to see that this recursive formula can easily be modified to DP.

这篇关于动态规划proboem最低成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！