在特定条件下将一组数字分配给N个组的算法

Question

3

假设我有一系列数字列表：

2,2,3,4,4

将数字分成N组（这里以3组为例）：

A:2,3 sum:5

B:4   sum:4

C:2,4 sum:6

我希望做的是将具有最高总和（此处为6）的组 - 具有最小总和（此处为4）的组减至最小化。

有没有人想到一种算法来实现这个目标？

另一个例子：

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

结果应该如下所示：

A:7,8,8 sum:23

B:7,8,9 sum:24

C:9,10  sum:19

- Billy

在第一个例子中，最小的组不应该是2吗？ - zaczap

我认为他想要最小化最高总和和最低总和之间的差异。他可以在问题陈述中使用一些括号。 - Baltimark

啊，这样更有意义，谢谢。 - zaczap

3个回答

1

考虑到即使 N 是二，这个问题也是 NP 完全问题，我可以给你一个非常糟糕的算法。

- MSN

0

Zweiterlinde的建议是查看bin packing。

我已经发布了这篇文章，但在输入完后意识到它是错误的。

您需要一种贪婪的方法，其中首先使用最大的数字。

这应该可以让您获得：从2,2,3,4,4 ...

group 1 (4): 4
group 2 (6): 4, 2
group 3 (5): 3, 2

并且从7、7、8、8、8、9、9、10 ...

group 1 (18): 10, 8
group 2 (24): 9, 8, 7
group 3 (24): 9, 8, 7

虽然我猜第二个例子可以写成19, 24, 23，这就使得这个答案是错误的。哼。

- Nerdling

当数字之间存在较大的间隔时，这种方法就会失效。考虑将(10,1,1,1,1,1,1,1,1)分成两组。你的算法输出为(10,1,1,1,1),(1,1,1,1)，而正确答案应该是(10),(1,1,1,1,1,1,1,1)。 - Welbog

嗯，我打完了才意识到，但还是决定发送出去。 - Jeremy L

无论如何，问题是NP完全的，所以如果你的算法有效，你会多赚一百万美元。 ;) - Welbog

是的！无论如何，动态规划都会有所帮助。 - Jeremy L

我的朋友问了我这个问题。乍一看似乎很简单，但实际上并不容易。 - Billy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- zweiterlinde · Accepted Answer

很遗憾，这个问题是NP难的。参见多处理器调度或装箱问题的相关文献。如果您对近似算法感兴趣，也许可以找到一些有用的信息。