时间戳

首页 > 解决方案 > 如何将浮点数列表分为两组进行优化，以使每组总和之间的差异最小化？

python - 如何将浮点数列表分为两组进行优化，以使每组总和之间的差异最小化？

问题描述

假设我有一个表单的浮动列表：

list = [a, b, c, d, e, f, ...]

我想将元素分类到两个列表（list_1 和 list_2）中，以使每个列表之和之间的差异最小化。我本质上是在尝试找出哪两个排列的大小彼此最接近。

编辑：“大小”是指两个子列表中的每一个的总和

标签： pythonalgorithmsorting

解决方案

我很想试试这个：（k是多少子列表）这段代码应该可以工作。

from typing import List

def partition(A: List[int], k:int) -> List[List[int]]:
    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(partition([2.5, 7.2, 4.3, 9.1, 12.4, 10.5, 8.6], 2))

Output:
[[12.4, 8.6, 4.3, 2.5], [10.5, 9.1, 7.2]]

推荐阅读