2

我有一个手机信号塔问题。有n个城镇。我们想在一些城镇建造手机信号塔。每个蜂窝塔都可以覆盖它自己和它的邻居。每个城镇都有建造手机信号塔的成本。我们想找出建造覆盖所有城镇的蜂窝塔的最低成本。

例如，

(1)

镇 1 2 3

COST 5 1 2 我们选择在 town-2 建造手机信号塔。费用为1。

(2)

镇 1 2 3 4

COST 5 1 2 3 我们选择在town-2/3建造手机信号塔。成本为 1+2=3。

(3)

镇 1 2 3 4

费用 5 1 3 2

我们选择在town-2/4 建造手机信号塔。成本为 1+2=3。

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

谢谢玲

4

1 回答 1

1

我会选择以下几行：

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是我们正在查看的当前城市数量，如果该城市已经被覆盖（从左边的城市），则布尔值为真。

  • 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(x,false)，最后一个城市在哪里x，你会得到最小的解决方案。
不难看出，这个递归公式很容易修改为DP。

于 2013-08-09T23:51:43.420 回答