Arp*_*ang 9 c++ algorithm optimization dynamic
实际问题是这样的:
麦当劳计划在一条直道上开辟一些关节(比方说n).这些接头需要仓库来存放食物.仓库可以存储任意数量的关节的食物,但必须仅位于其中一个关节.McD拥有数量有限的仓库(比如k),并希望将它们放置在最小化距离最近仓库的平均距离的位置.
给定关节坐标的数组(n个元素)和整数'k',返回一个'k'元素数组,给出仓库最佳定位的坐标.
对不起,我没有任何可用的例子,因为我是从记忆中写下来的.无论如何,一个样本可能是:
array = {1,3,4,5,7,7,8,10,11}(n = 9)
k = 1
答案:{7}
这就是我一直在想的:对于k = 1,我们可以简单地找出集合的中位数,这将给出仓库的最佳位置.但是,对于k> 1,给定集合应分为"k"子集(不相交,以及超集的连续元素),每个子集的中位数将给出仓库位置.但是,我不明白应该在什么基础上形成'k'子集.提前致谢.
编辑:这个问题还有一个变化:取代sum/avg,最小化一个关节和它最近的仓库之间的最大距离.我也没有得到这个..
笔直的高速公路使这成为动态规划的练习，沿着高速公路从左到右工作。部分解决方案可以通过最右边仓库的位置和放置的仓库数量来描述。部分解决方案的成本将是到最近仓库的总距离（对于固定 k 最小化，这与最小化平均值相同）或迄今为止到最近仓库的最大距离。
在每个阶段，你都已经计算出了最左边 N 个节点的答案，并根据使用的仓库数量和最右边仓库的位置对它们进行索引 - 你只需要节省最好的成本。现在考虑下一个关节，并使用您为 N 个关节存储的答案来加快 N+1 个关节以及 k 和最右边仓库的所有可能值的最佳解决方案。一旦您制定出涵盖所有节点的最佳成本解决方案，您就知道其最右边的仓库在哪里，这将为您提供一个仓库的位置。返回到将该仓库作为最右侧关节的解决方案，并找出该解决方案基于什么解决方案。这为您提供了一个最右边的仓库 - 因此您可以返回所有仓库的位置以获得最佳解决方案。
我倾向于错误地计算出这个问题的成本，但是有 N 个关节和 k 个仓库来放置，你需要采取 N 个步骤，每个步骤都基于不超过 Nk 个先前的解决方案，所以我认为成本是 kN^2。