是否将一个数组分成两半，且总和P或NP相等？ [英] Is partitioning an array into halves with equal sums P or NP?

问题描述

这是关于分区问题的算法面试问题。

This was an algorithm interview question about the Partition Problem.

您将得到一个数组，其中包含
个数字，在0到5位数字之间。
编写一个函数，该函数将返回是否可以将数组
分为两半，以使
的两半之和相等。

You are given an array which consists of numbers with between 0 and 5 digits. Write a function which will return whether the array can be divided into 2 halves such a that sum of the two halves would be equal.

这是NP问题还是可以通过动态编程解决？

Is this an NP problem or can it be solved by dynamic programming?

0到5位之间表示0 〜99999，我想。

"between 0 and 5 digit" means 0 ~ 99999, I think.

我在此处。

推荐答案

两者。问题出在NP，我很确定可以通过动态编程在伪多项式时间内解决它。

Both. The problem is in NP, and I'm pretty sure it can be solved in pseudo-polynomial time with dynamic programming.

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

一般问题是NP完全的，可以通过动态编程在伪多项式时间内求解。 T

The general problem is NP-complete, and can be solved in psuedo-polynomial time with dynamic programming. T

这个特定的限制（0-5位数字）可能不是NP完整的。不管怎样，0位数字是什么？

This specific restriction of it to numbers of 0-5 digits probably isn't NP-complete. What's a 0-digit number, anyway?

通常，对于分区问题，无需要求分区大小相等，并且分区总和相等。但是在这里您说分为2个一半，我不确定一半是指数组的一半，还是只是总数的一半。

Usually for the partition problem there is no requirement that the partitions be of equal size, just that they have equal sum. But here you say "divided into 2 half", I'm not sure whether "half" is intended to mean half the array, or just to mean half the total.

我猜想这种差异（如果是差异）可能不会影响DP解决方案的复杂性，但我不确定。我没有任何一种临时证明，而且，嗯，是的，看起来就像您可以使用DP进行的事情，我必须考虑一下。

I'd guess that this difference, if it is a difference, probably doesn't affect the complexity of the DP solution, but I'm not sure. I don't have a proof either way off-hand, beyond, "um, yeah, looks like the kind of thing you can do with DP, I'd have to think about it".

这篇关于是否将一个数组分成两半，且总和P或NP相等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！