最小化和之间的差
最小化和之间的差
提问于 2014-01-10 23:49:51
假设您有一个8种价格的清单--例如：
1$
2$
3$
4$
5$
6$
7$
8$你想把价格分成两组，每组4元。
让一个团体的总价格是该集团的个别价格之和。你如何划分集团，使两个总价格之间的差距尽可能小？
显而易见的解决办法是尝试所有的配对，看看哪一个是最低的，但是如果这个方案扩展到超过8个价格或超过2个组，那么是否有一个更有效的解决方案呢？
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-01-11 00:11:59
看起来很无辜，但这是个超级棘手的问题。
显而易见的解决办法是尝试所有的配对，看看哪一个是最低的，但是如果这个方案扩展到超过8个价格或超过2个组，那么是否有一个更有效的解决方案呢？
只要P != NP：不，一般没有有效的(多项式)解。而明显的解(AKA蛮力)具有指数复杂性.
设N=价格数，K=子集数。
K=2的分区问题已经是NP-完全的.因此，广义版本也是NP-完全的.如果要找到一个有效的(多项式)算法，那就意味着P= NP。
你可以尝试次优解，它们会更快，但没有最优解的保证。对于K=2，维基百科描述了伪多项式时间动态规划算法。对于K>2：
3-划分问题与划分问题有很大的不同，除非P= NP，否则不存在伪多项式时间算法。有关分区问题的概括，请参见装箱问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21056592
复制相关文章
相似问题
腾讯云开发者
