设施选址的动态规划算法

Question

在a_1，a_2，.，a_n沿线有n所房屋。我们希望沿着同一条线设置porta便盆，这样每个房子都在距离R至少一个porta便盆的范围内。这些便盆仅限于指定的位置( b_1，b_2，.，b_m )。让c_i作为在location b_i上设置porta便盆的成本。

找到一个动态规划算法，以最小化设置porta便当的总成本。该算法应该能够检测一个解决方案是否不存在。假设所有的a和b值都是不同的。

投入：

• A1，2岁，...n负责房子的位置
• B1，2，...m持有潜在的便池位置
• C1，2，...m负责在每个位置设置一个端口便盆的费用。

输出:在约束条件下放置便盆的最低成本，即每所房子必须在距离某个porta便盆的距离范围内。

我很难找到要处理的递归表达式。任何帮助都将不胜感激！

Answer 1

你的问题让我有机会为类似的问题编写一些代码，这类问题经常出现在手机塔的放置问题或手机基本覆盖问题上。

伪码如下：

1) Sort houses in ascending order
2) Sort facilities positions and their costs in ascending order by facilities positions
3) Let dp(i) be the minimum cost to cover i houses and lastBase(j) the last base used to cover j houses
4) Set the base case dp(0) = 0 and lastBase(0) = -1
5) For each house i:
6)   Check if previous solution is either valid or in range of this new house
7)   if it is -> grab it as solution
8)   else
9)     find a new base starting from lastBase(i) + 1 which can cover this house
10)    let it be the minimum-cost one
11)  if a base could be found -> add it to the previous solution
12)  else -> Problem cannot be solved

我建议你先试一试。

为了完整起见:解释、图像和C++代码可在这里找到。

欢迎反馈或错误。

Answer 2

我将给你一个如何进行，你如何编码，这是由你自己的想法。

给定A，B，C (也假设A和B中的所有元素都在数列上)-

-> Sort A in ascending order.

-> Sort B and C together(as they are dependent) based on B's values in ascending order. 

-> Maintain a temp array(size n) which keeps track of which "porta potty" 
  an A element belongs to,by mapping to the "porta potty" index.

-> Now take each element from B and move both forward and backward R steps from that 
   point on the number line.

-> If any A element is found in those R steps(on the number line) 
   AND if(and only if) it does not presently belong to any "porta potty" OR 
   the cost of setting up the current "porta potty" element is more than the "porta potty" 
   it(A element) already belongs to, then only shall you set the value in temp array 
   for that A element to the current "porta potty" index number.

-> Now once we are done with all B points, do the following

-> Traverse the temp array and push the "porta potty" index numbers we have into a set

-> You now have a list of all the "porta potty" indices which are the cheapest
   yet crucial to be placed.

想一想，如果有什么事情你不清楚，请告诉我。另外，排序部分只是为了提高性能。

Answer 3

这个是手机塔放置问题。我想你的应该是相似的。

​

​