动态编程问题以最低的成本 [英] Dynamic programming problem 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）

成本5 1 2
我们选择构建镇2中的手机塔。费用为1。

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

（2）

成本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）

成本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?

感谢
Ling

Thanks Ling

推荐答案

我会在以下几行中添加一些内容：

I'd go with something among the following lines:

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]}

想法是：

x 是我们正在查看的城市的当前数量，如果该城市已被覆盖（从左边的城市开始），则布尔值为true。

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，false）是不覆盖城市1的基础，因此您必须在此处放置塔楼，而 f（ 1，true）是覆盖1号城市的基地，因此您不需要塔楼就可以了。


• f（x，true）表示城市x已被覆盖，因此您可以放在那里一座塔楼，然后继续到下一个城市[也已覆盖- f（x-1，true）]，或者不要在那儿放塔楼，下一个不覆盖城市[ f（x-1，false）]


• f（x，false） 是不包括城市x的情况，因此您基本上有两个选择，或者在其中放一个塔，然后继续 f（x-1，true）。或在下一个城市（在x-1中）放置一座塔，然后继续 f（x-2，true）

• 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.

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