python - 将一个数组划分为 k 个分区子数组,这些子数组具有最小的差异
问题描述
我有一个问题:给定一个数组 a1..aN 一个非负 K, (K<N)
. 将数组划分为 K 个具有最小差异的分区子数组。之后,列出找到的优化子数组。例如:输入:a=[1,2,3,4,7], K=3
输出:{1,4}, {2,3}, {7}
解释:1+4=5, 2+3=5, 7=7
=>差异=2是最小值=>选择
解决方案
您所说的问题的最佳解决方案是 NP-hard,但这里有一个简单的天真方法,在许多情况下都做得很好:
def naive_partition(a, k):
result = [[] for _ in range(k)]
sums = [0] * k
for x in sorted(a, reverse=True):
i = sums.index(min(sums))
sums[i] += x
result[i].append(x)
return result
print(naive_partition([1, 2, 3, 4, 7], 3))
结果:
[[7], [4, 1], [3, 2]]
推荐阅读
- postgresql - Postgres 未在 swarm 服务器重新启动时启动
- javascript - 悬停时淡出一个元素并淡入另一个元素
- python - Pyomo:是否可以仅将定义的值分配给设计变量?
- sql - 在excel SQL查询中堆叠列数据
- javascript - 试图理解为什么在通话结束时会有额外的括号
- angular - angular 7 库中的时刻 js 出错
- amazon-web-services - 何时使用 AWS Lambda,何时使用 Kubernetes (EKS)?
- c++ - 推导模板化类参数的模板参数:const 问题
- spring-boot - Wiremock 请求模式与请求参数匹配
- android - 获取给定 AccessibilityNodeInfo 的滚动方向