最小化总和之间的差异 [英] Minimizing the difference between sums

问题描述

假设您有一个包含 8 个价格的列表 - 例如:

Lets say you have a list of 8 prices - for example:

1$
2$
3$
4$
5$
6$
7$
8$

您想将价格分成 2 组，每组 4 个价格.

You want to divide the prices into 2 groups of 4 prices each.

让一个组的总价格为该组单个价格的总和.您如何划分组，使两个总价之间的差异尽可能小?

Let the total price of a group be the sum of the individual prices of the group. How do you divide the group such that the difference between the two total prices is as small as possible?

显而易见的解决方案是尝试所有对，看看哪一个是最低的，但如果将其扩展到超过 8 个价格或超过 2 个组，是否有更有效的解决方案?

The obvious solution is to try all the pairs and see which is the lowest, but is there a more efficient solution that could work if this were extended to more than 8 prices or more than 2 groups?

推荐答案

看起来很无辜，但这是一个超级困难的问题.

Looks really innocent, but it's a super hard problem.

显而易见的解决方案是尝试所有对，看看哪个是最低，但是否有更有效的解决方案，如果这样做扩展到超过 8 个价格或超过 2 个组?

The obvious solution is to try all the pairs and see which is the lowest, but is there a more efficient solution that could work if this were extended to more than 8 prices or more than 2 groups?

只要P != NP:不，一般没有效率(多项式)解决方案.显而易见的解决方案(AKA brute-force)具有指数级的复杂性.

As long as P != NP: No, generally there is no efficient (polynomial) solution. And the obvious solution (AKA brute-force) has exponential complexity.

设 N = 价格数，K = 子集数.

Let N = number of prices and K = number of subsets.

K=2 的分区问题 已经是 NP-complete.所以，广义版本也是NP完全的.如果有人会找到一种有效的(多项式)算法，那就意味着 P = NP.

Partition problem for K=2 is already NP-complete. So, generalized version is also NP-complete. If one would found an efficient (polynomial) algorithm, that would mean that P = NP.

您可以尝试使用次优解决方案，它们会更快，但无法保证最佳解决方案.对于 K=2，维基百科描述了伪多项式时间动态规划算法.对于 K>2:

You can try with sub-optimal solutions, they will be much faster, but without a gurantee of optimal solution. For K=2 Wikipedia describes pseudo-polynomial time dynamic programming algorithm. For K>2:

三分区问题与分区问题完全不同并且没有伪多项式时间算法，除非 P = NP.为了分区问题的概括，请参阅装箱问题.

The 3-partition problem is quite different than the Partition Problem and has no pseudo-polynomial time algorithm unless P = NP. For generalizations of the partition problem, see the Bin packing problem.

这篇关于最小化总和之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！