动态规划：递归关系

我想写一个动态规划算法，解决以下问题;为此，我想定义适当的递推关系。这是问题的陈述：考虑我们寻求放置电话天线的一段长度为K英里的直道。可用网站的特点是整数x1，x2 ,. 。。，xn其中xi表示沿道路的天线（0≤xi≤K）的英里位置。另外，位于位置xi的天线产生r（0≤i≤n）的收益。两个连续天线之间的距离不能小于或等于5公里。如何以及在哪里放置天线以最大化您的收入。动态规划：递归关系

这里的递推关系，我写：可变参数是： K：道路 xi的长度：天线 XI-x的位置（i +1）> 5

这是以最大化要放置的天线的数量。因此，设N是要放置的天线的数量。那么N取决于k和xi。首先，如果第一个天线放置在位置xi处，那么就有K公里的地方可以放置天线。天线将放置在位置5 + xi的旁边，然后它将保持k-5公里xi，从而可以放置天线。如果我决定不种植位置xi的天线，那么我可以将它们放在位置5 + xi。

因此我的下列递推关系： N（K，I）= MAX（NXI，K）+ N5 + XI，N（XI，在）& & N（XI，在）

是正确？谢谢。

这是我的算法（我想在为O（n算法））：

Algorithm Antenna(\emph{int K, int xi, int profit) 
{ 
int K: road lenght 
int xi: position of antenna i 

While{j < k} 
{ 
    xi = j 
    if{xi < k} 
    { 
     return idealPosition 
    } 
    j = j+5 
    return profit 
} 
}

关于利润，你有天线的越多，你有更多的利润。

来源

2011-04-22 cProg

问题陈述很可能是不完整的---收入如何取决于距离？天线是否有成本？ – 2011-04-22 19:11:38

我没有得到关于最大化放置的天线数量的部分。你不想让收入最大化吗？ – hugomg 2011-04-23 02:13:29

大家好，关于利润，你有天线越多，你有更多的利润;那么你是对的，我想最大化它。 – cProg 2011-04-24 14:38:16

是否真的只能安装天线作为特定的站点？

我假设您的网站按顺序编号。（i）从i = 1开始，你可以使用

（a）在第i个位置放置一个天线，总分为1+只使用剩余站点的最佳分数，也就是说，距离我5英里以外的所有站点j （j> i）（b）不要将天线放置在位置i，而是将它放置在i + 1处。总分再次为1+，无论您只能使用剩余的网站。

最佳解决方案是max（a，b）

来源

2011-04-22 18:26:32 mbatchkarov

动态规划：递归关系

回答

相关问题