如何将数组划分为最小和差的组?

I have array of integers, I need to sort them in unknown number of groups with minimal difference in sum of each group.

我有一个整数数组，我需要对它们进行排序，在每个组中最小差异的组中进行排序。

example:

例子:

Array: 2, 1, 4, 7, 1, 2, 6, 8
Number of groups = 3
Result:
Group 1 – 8, 2 = 10
Group 2 – 7, 2, 1 = 10
Group 3 – 6, 4, 1 = 11

Is there any alghoritham too solve this problem? I'm stuck.

有什么算法能解决这个问题吗?我卡住了。

1 个解决方案

#1

Firstly, if the number of groups is 2 this reduces to the subset sum problem variant the partition problem. This proves the problem is NP-hard, so you shouldn't try to find an efficient algorithm.

首先，如果组的数量是2，这就减少到子集和问题的变体的分区问题。这证明了这个问题是np困难的，所以你不应该试图找到一个有效的算法。

Given that it will be at least exponential you might as well just generate all permutations and pick the best. I know some people don't like recursion, but it really is useful here for enumerating the group possibilities:

考虑到它至少是指数级的，你也可以产生所有的排列并选出最好的。我知道有些人不喜欢递归，但这里确实很有用，可以列举出群体的可能性:

recfunc(array, groups):
    if array is empty
        return an array containing the element groups
    else
        groupsList = empty array
        foreach aGroup in groups
            element = array[0]
            groupsList += recfun(array - element, groups where aGroup adds element)
       return groupsList

This algorithm will create a list of all possibilities. It is fairly inefficient, but shouldn't be too hard for you to implement. From here just go through the list and calculate if the sum of the groups is the minimum of the list.

该算法将创建所有可能的列表。它是相当低效的，但是不应该太难实现。从这里开始计算列表，并计算组的和是否为列表的最小值。

#1