给定一个包含 n 个正整数（n 个偶数）的列表，将该列表分成两个子列表，以使两个子列表中整数之和之间的差异最小化。这是一个 NP 完全问题还是一个 NP 难题？
1 回答
0
TL；DR - 这很难。
这是分区问题的优化版本。分区问题是决定是否可以将给定的正整数列表分为 2 个子集，以便子集的总和相等。优化版本要求最小化差异（就像你问的那样）。
分区问题是 np 完全的，但优化是 np 困难的。
您可以在 wiki 中阅读有关这些问题的更多信息： https ://en.wikipedia.org/wiki/Partition_problem
于 2016-09-17T22:19:55.760 回答