我正在努力解决上面的问题,我有一个数组,例如[1,2,4,5],我想把它分成k个子数组,这样这些子数组的最大大小就是可能的最小值例如,对于k=3,这将是:
[5] [4,1] [3,2]
max(...) = 5
我能找到的唯一类似的东西是:https://www.geeksforgeeks.org/split-the-given-array-into-k-sub-arrays-such-that-maximum-sum-of-all-sub-arrays-is-minimum/
但是,对于上面的例子,它没有给出正确的结果,也没有返回数组,这是我的情况所需要的。
理想情况下,我想在Python中做到这一点,但伪代码也可以在中工作
非常感谢您对此的任何帮助
如果您有一个长度为L的数组,并且需要分离成k子集,则最终会得到长度为L'=int(L/k(和长度为L'=L%k=(L-L%k(/k子数组。如果对数组x = np.sort(x)
进行排序,则长度为l'的子数组将是具有x
的最右边元素和l’-1最左边元素的子数组。其他n数组以类似的方式构建,总是将最右边的元素与L'-1最左边的元素组合在一起。
我认为这应该给出正确的答案,因为最右边的元素总是最大的,最小的组合总是与数组中最左边的元素在一起。任何其他组合都相等或更大。
在您的示例中,数组已经排序,它应该给出长度为l'=2的l'=1和5
,n=2,这将是[4,1]
,然后是[3,2]
。