给定一个整数数组,找到一组至少一个总和为0的整数.
例如,给定[-1, 8, 6, 7, 2, 1, -2, -5],算法可以输出,[-1, 6, 2, -2, -5]因为这是输入数组的子集,其总和为0.
解决方案必须在多项式时间内运行.
在多项式时间内你很难做到这一点,因为这个问题被称为子集和问题,并且已知是NP完全的.
但是,如果你确实找到了一个多项式解决方案,那么你将解决" P = NP？ "问题,这将使你变得非常富有.
你得到一个已知多项式解的最接近的是一个近似值,例如维基百科上列出的那个,它会尝试给你一个接近但不一定等于0的答案.
| 归档时间： |
|
| 查看次数： |
4874 次 |
| 最近记录： |