实际问题如下:
麦当劳计划沿着一条直路开设多个连锁店(假设有n个)。这些店需要仓库来存储食物。一个仓库可以为任意数量的店提供存储,但必须只能位于其中一个店中。 麦当劳只有有限数量的仓库(假设为k),并希望将它们放置在使店到最近仓库的平均距离最小的位置。
给定一个长度为n的坐标点数组和整数“k”,返回一个长度为'k'的数组,其中包含最佳仓库位置的坐标。
抱歉,我没有可用的示例,因为我是凭记忆写下这些内容的。无论如何,可以使用以下样本:
数组={1,3,4,5,7,7,8,10,11} (n=9) k=1
答案:{7}
我一直在想:对于k=1,我们可以简单地找出集合的中位数,这将给出仓库的最佳位置。但是,对于k>1,应将给定集合分成'k'个子集(不相交,并且由超集的连续元素组成),并且每个子集的中位数将给出仓库位置。但是,我不明白应根据什么基础形成'k'个子集。提前感谢。
编辑:此问题还有一个变体:不是最小化总和/平均值,而是最小化店铺与其最近仓库之间的最大距离。我也不明白这个问题。
麦当劳计划沿着一条直路开设多个连锁店(假设有n个)。这些店需要仓库来存储食物。一个仓库可以为任意数量的店提供存储,但必须只能位于其中一个店中。 麦当劳只有有限数量的仓库(假设为k),并希望将它们放置在使店到最近仓库的平均距离最小的位置。
给定一个长度为n的坐标点数组和整数“k”,返回一个长度为'k'的数组,其中包含最佳仓库位置的坐标。
抱歉,我没有可用的示例,因为我是凭记忆写下这些内容的。无论如何,可以使用以下样本:
数组={1,3,4,5,7,7,8,10,11} (n=9) k=1
答案:{7}
我一直在想:对于k=1,我们可以简单地找出集合的中位数,这将给出仓库的最佳位置。但是,对于k>1,应将给定集合分成'k'个子集(不相交,并且由超集的连续元素组成),并且每个子集的中位数将给出仓库位置。但是,我不明白应根据什么基础形成'k'个子集。提前感谢。
编辑:此问题还有一个变体:不是最小化总和/平均值,而是最小化店铺与其最近仓库之间的最大距离。我也不明白这个问题。