提出多项式算法

给定n个检查，每个任意（整数）货币值，决定检查是否可以分成具有相同货币值的两个部分。提出多项式算法

我非常想到如何解决这个问题。有没有一种算法可以在多项式时间内解决这个问题，还是NP-Complete？

2017-01-27 mocode9

可能是这个问题最好放在[编程拼图]（http://codegolf.stackexchange.com/）或[令人费解]（http://puzzling.stackexchange.com/） – yaitloutou

@yaitloutou我认为这个问题在这里比在迷惑或编程谜题中讨论得多。最多也许应该发布到cs.stackexchange.com – user31264

@ user31264谢谢你的澄清 – yaitloutou

是的，这是一个NP完整的问题。它是the subset sum problem的变体。

2017-01-27 01:31:39 Gene

真棒谢谢你！我很困惑这一点。好奇如果我有两个不同值的N检查。例如值X和值Y.那么对于这个任何算法是NP完成？ – mocode9

对于两个不同的值，可以求解简单的丢番图方程。在一般情况下，存在使用动态编程的伪多项式算法。 – MBo

你错了，这可以通过使用动态规划的多项式复杂性来完成。 –

事实上，你可以使用动态规划在O（n * sum/2）中解决这个问题，首先将所有检查总结为varaibel总和，然后你可以对检查值执行dp（接受或离开它或采取它），并在最后检查这个总和是否等于s/2。

2017-01-27 13:11:28

回答