需要将一个正值列表分成K个组。组的大小（值的数量）应该几乎相等，但每组中项目的值具有最小标准差。（考虑按相似定价对产品进行分组）。我在想，先对值排序，然后按顺序分成K组，这样会非常接近，只有当组的大小不相等时，才进行一次遍历，看看从一个组移动到下一个组的额外项目是否会产生更好的结果。但我觉得我在这里遗漏了一些重要的东西，它应该比这更复杂。
webghufk1#
你漏掉了一个并发症。假设k是偶数，n = 2.5*k是偶数，那么你的组中有一半的大小是2，一半的大小是3，用一种简单的方法，你必须考虑k choose 2 = O(2^k / sqrt(k))种可能的方法来决定哪些是2，哪些是3，这将需要指数时间。令m为向下舍入的组大小，则将前i项最优划分为j组将是在最后一组中具有m元素并且将前i-m项划分为j-1组，或者在最后一组中包含m+1元素，并将前i-m-1项划分为j-1组。您可以使用递归函数计算，该函数返回(cost, linkedListOfChoices)的对。给递归增加一个缓存层，它将在多项式时间内运行，这被称为自顶向下动态编程。从用于将整个列表划分为k组的最佳linkedListOfChoices到实际的组应该是简单明了的。假设我们想把[0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0, 2.1, 2.3]分成4组，你应该得到一个链表，它对应于（但是可能有非常不同的表示）：
k
n = 2.5*k
k choose 2 = O(2^k / sqrt(k))
m
i
j
i-m
j-1
m+1
i-m-1
(cost, linkedListOfChoices)
linkedListOfChoices
[0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0, 2.1, 2.3]
4
[8, 9, [5, 7, [2, 4, [0, 1, null]]]]]
从你的分组（读里面出来，把指数变回数字）是：
[[0.1, 0.2], [0.4, 0.5, 0.6], [0.8, 0.9, 1.0], [2.1, 2.3]]
wvt8vs2t2#
先排序的想法是正确的。然后你必须从排序后的数组中创建K个组，你可以这样做：如果有任何偏差，你可以发挥周围的“边界元素”的每一组，使结果更好。例如：N=16，K=3。现在有一些可能的结果。第一组5个成员，第二组6个成员，最后一组5个成员，但还有其他可能性来创建您的组。现在您需要找到并评估所有可能性，并选出最佳的一个。例如，如果形状[5，5，6]比形状[5，6，5]你把最后一个元素（“边框元素”）从第二组移到第三组。如果完全没有偏差，例如N=100，K=10，那么你只能选择一种可能性，在这种情况下，这是最好的一种。
2条答案
按热度按时间webghufk1#
你漏掉了一个并发症。
假设
k是偶数，n = 2.5*k是偶数，那么你的组中有一半的大小是2，一半的大小是3，用一种简单的方法，你必须考虑k choose 2 = O(2^k / sqrt(k))种可能的方法来决定哪些是2，哪些是3，这将需要指数时间。令
m为向下舍入的组大小，则将前i项最优划分为j组将是在最后一组中具有m元素并且将前i-m项划分为j-1组，或者在最后一组中包含m+1元素，并将前i-m-1项划分为j-1组。您可以使用递归函数计算，该函数返回(cost, linkedListOfChoices)的对。给递归增加一个缓存层，它将在多项式时间内运行，这被称为自顶向下动态编程。
从用于将整个列表划分为
k组的最佳linkedListOfChoices到实际的组应该是简单明了的。假设我们想把
[0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0, 2.1, 2.3]分成4组，你应该得到一个链表，它对应于（但是可能有非常不同的表示）：从你的分组（读里面出来，把指数变回数字）是：
wvt8vs2t2#
先排序的想法是正确的。然后你必须从排序后的数组中创建K个组，你可以这样做：如果有任何偏差，你可以发挥周围的“边界元素”的每一组，使结果更好。
例如：N=16，K=3。现在有一些可能的结果。第一组5个成员，第二组6个成员，最后一组5个成员，但还有其他可能性来创建您的组。现在您需要找到并评估所有可能性，并选出最佳的一个。例如，如果形状[5，5，6]比形状[5，6，5]你把最后一个元素（“边框元素”）从第二组移到第三组。
如果完全没有偏差，例如N=100，K=10，那么你只能选择一种可能性，在这种情况下，这是最好的一种。