您有两个整数列表 A={1,3,60,24} 和 B={14,54,3}，顺序和列表长度未确定。将 A 中的数字放入 B 中的最佳策略是什么，以便 B 中结果的方差尽可能平衡。如果没有可用空间，您不必将 A 中的所有数字都放入 B。但是如果有可用空间，您必须输入数字
我正在考虑应用分支定界，但是，我不确定如何找到修剪条件，例如计算子问题的方差（未完全填充）来判断要剪切哪个分支？
有任何想法吗？
问问题
4607 次
2 回答
1
您描述的问题是分区问题（http://en.wikipedia.org/wiki/Partition_problem）。找到最佳解决方案是 NP 完全的，但是对于大多数情况，有许多近似值几乎是完美的。
事实上，你描述的算法是操场上的孩子们挑选球队的方式。如果集合中的数字具有相似的数量级，则该贪心算法的性能非常好。当然，这不是最好的解决方案，但考虑到问题是 NP 完全的，它的简单性真是太棒了。
American Scientist 上的这篇文章对这个问题进行了很好的分析，你应该仔细阅读它：最简单的难题（http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-问题）。
于 2013-03-07T14:04:08.920 回答
0
从 C[i]=A[i]-B[i] 的 A 和 B 之间的差异创建列表 c。然后你应该找到它们之和接近于零的所有元素。就像这个问题一样。但在这个问题中你有一个负数。你必须找到一个子集，它们的总和接近于零。我认为这是一个 NP 完全问题。
于 2013-03-07T07:27:55.757 回答