将一个数组分成两半使它们的和相等是P问题还是NP问题？

Question

这是一个有关分区问题的算法面试题。

给定一个由0到5位数字组成的数组，编写一个函数来返回是否可以将该数组分成两个部分，使得这两个部分的和相等。

这是一个NP问题还是可以通过动态规划来解决？

“0到5位数字”意味着0~99999，我认为。

---

我在SO之外找到了一个很好的答案，链接在此here。

- Josh Morrison

---

这些半部分必须是相邻的吗？还是只是一些任意的分割？ - Gumbo

@Gumbo♦ 我认为它可以是任意的。 - Josh Morrison

Answer 1

这显然是NP问题 - 解决方案可以在多项式时间内验证。

但它不是NP完全问题，因为元素是有界的（数字范围在0到5位数之间）。

已知该问题会经历“相变”，当 m / n < 1 时容易解决，否则难以解决。

- Mark Byers

Answer 2

面试问题的设计不仅仅是为了测试解决问题的能力，也包括问题分析。因此，这个问题并不够具体。

我可以选择任意两个元素子集，还是它们必须是一致的部分？如果是前者，那么这个问题就是NP完全问题（更多信息请参见http://en.wikipedia.org/wiki/Partition_problem），如果是后者，那么显然它是微不足道的（面试问题通常以微不足道的编程任务结束）。

如果一般问题是NP完全的，也许我们可以尝试专门化它？我们对数组了解多少呢？ 也许我们可以通过做一些外部假设来简化问题？

我认为这是面试官希望处理这类问题的方式。

更新：对于指定的数字范围，该问题等同于离散背包问题（背包的大小限制为整个数组和大小的一半，大小为100000的权重集，这意味着我们可以在O(n)时间内解决它） 有关背包问题的更多信息，请参见http://en.wikipedia.org/wiki/Knapsack_problem。

- Rafał Rawicki

Answer 3

两者都是。这个问题属于NP问题，我相信可以用动态规划算法在伪多项式时间内解决。

http://en.wikipedia.org/wiki/Partition_problem

这个一般性问题是NP完全问题，可以通过动态规划在伪多项式时间内解决。

将其限制为0-5位数字可能不是NP完全问题。反正什么是0位数字呢？

通常对于分割问题，没有要求分割的部分大小相等，只要它们的和相等即可。但是在这里，您说“分成两半”，我不确定“半”是否意味着数组的一半，还是总数的一半。

我猜想，如果有区别的话，可能不会影响DP解决方案的复杂性，但我不确定。我没有证明，只能说，“嗯，看起来像是可以用DP解决的问题，我需要思考一下。”

- Steve Jessop

---

0到5位数范围意味着0~99999，我想。 - Josh Morrison

Answer 4

你可以将这个算法应用到分区问题上，不需要太多修改。

线性算法解决求和子集 NP-完全问题的纯 Python 实现

https://github.com/maxtuno/Universal/blob/master/linear_sum_subset_algorithm_oscar_riveros.py

#!/usr/bin/env python3

__author__ = "O. A. Riveros"
__copyright__ = "Copyright 2014, O. A. Riveros, All right reserved"
__license__ = "MIT"
__email__ = "[e-mail]"

"""
O. A. Riveros
http://independent.academia.edu/oarr
http://twitter.com/maxtuno
"""

"""
first 100 primes
"""
data = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

solution = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

"""
for custom entertainment
solution = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
"""

target = sum([data[i] for i in range(len(solution)) if solution[i] == 1])

l = len(data)

size = len('{0:b}'.format(sum(data)))

def rotate(l,n):
    return l[n:] + l[:n]

def slice(l, n):
    return list(int(l[i:i+n], 2) for i in range(0, len(l), n))

data_second_order = []
for i in range(l):
    data_second_order += rotate(data, i)

T = 0
for i in range(l):
    T += int(''.join('{0:b}'.format(k).zfill(size) for k in rotate(data_second_order, i)), 2)
    t = slice('{0:b}'.format(T).zfill(size*(l**2)), size)
    if (target in t):
        '''
        for review the results
        print('The target {} found in {} steps from {}.'.format(target, i + 1, t))
        '''
        print('The target {} found in {} steps'.format(target, i + 1))
        break

"""
The target 24133 found in 100 steps
"""

- user2532519

Answer 5

没错，如果集合中的数字是有界的，那么问题就变成了多项式复杂度。

您可以使用二分查找技术。

阅读 Partition_Problem 的维基页面，然后在开头，您会发现对几乎等效的 Subset_Sum_Problem 的引用。您也应该找到有意义的阅读维基页面。

- Martin Carames Abente