Come up with polynomial algorithm

Question

Given n checks, each of arbitrary (integer) monetary value, decide if the checks can be partitioned into two parts that have the same monetary value.

I'm beyond mind blown on how to solve this. Is there an algorithm to solve this in polynomial time or is this NP-Complete?

may be this question is better placed in programming puzzle or puzzling — yaitloutou
– yaitloutou, Commented Jan 27, 2017 at 1:21
@yaitloutou I think the question is much more on-topic here than in puzzling or programming puzzle. At most, maybe it should be posted to cs.stackexchange.com — user31264
– user31264, Commented Jan 27, 2017 at 10:03

Gene · Accepted Answer · 2017-01-27 01:31:39Z

2

Yes it's an NP complete problem. It's a variation of the subset sum problem.

answered Jan 27, 2017 at 1:31

Gene

47.1k4 gold badges64 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

mocode9 Over a year ago

Awesome thank you! I was puzzled on this for so long. Curious what if I had N checks of two different values. For example value X and value Y. Then would any algorithm for this be NP complete?

MBo Over a year ago

For two different values you can solve simple Diophantine equation. In general case there are pseudo-polynomial algorithms using dynamic programming.

Abdennacer Lachiheb Over a year ago

You are wrong, this is can be done with a polynomial complexity using dynamic programming.

Gene Over a year ago

@AbdenaceurLichiheb Sorry you're wrong. This is called a "weakly NP complete problem." It can be solved by a dynamic program in time proportional to the magnitude of the numbers. If the numbers aren't limited range, this requires time exponential in the size of the inputs.

Abdennacer Lachiheb Over a year ago

Yeah, you are right I didn't know about "weakly NP complete problem" tell know, i thought knapsack problem is not an NP-complete problem, well sorry about calling you're solution wrong!

|

Abdennacer Lachiheb · Accepted Answer · 2017-01-27 13:11:28Z

Actually you can solve this in O(n*sum/2) using dynamic programming, first sum up all checks into a varaibel sum, then you can perform dp on the checks values (either take it or leave it or take it) and check at the end if that sum is equal to s/2.

Still, this isn't P because sum grows with n. Since the algorithm either takes or leaves a check, for every check, there is exponential complexity.

Collectives™ on Stack Overflow

Come up with polynomial algorithm

2 Answers 2

6 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

1 Comment

Related