算法的某些条件下，一个数字列表分配给N个组 [英] Algorithm to allocate a list of numbers to N groups under certain condition

问题描述

让我们说我有一个数字列表：

2,2,3,4,4

拆分号码分成N个组（3组在这里作为一个例子）：

A：2,3总和：5 B：4-总和：4 C：2,4总和：6

我要的是尽量减少本集团的最高金额（6这里） - 该组最小的总和（4这里）

有谁想到一个算法来实现这一点？

---

另外一个例子：

7,7,8,8,8,9,9,10

结果应该如下：

A：7,8,8和：23 B：7,8,9和：24 C：9,10总和：19

解决方案

不幸的是，这个问题是NP难。请参阅多处理机调度或的装箱。您可能还能够找到一些有用的近似算法，如果你有兴趣的这一做法。

Let's say I have a list of numbers:

2,2,3,4,4

Split the numbers into N groups (3 groups here as an example):

A:2,3 sum:5

B:4   sum:4

C:2,4 sum:6

What I want is to minimize the group with the highest sum (6 here) - the group with the smallest sum (4 here).

Does anyone think of an algorithm to achieve this?

---

Another example:

7,7,8,8,8,9,9,10

The result should be as follows:

A:7,8,8 sum:23

B:7,8,9 sum:24

C:9,10  sum:19

解决方案

Unfortunately, this problem is NP hard. See references for multiprocessor scheduling or bin packing. You may also be able to find some useful approximation algorithms, if you're interested in that approach.

这篇关于算法的某些条件下，一个数字列表分配给N个组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！