I have looked at the problem and found some solutions but so far they seem to be NP, I believe I can make a sufficiently fast algorithm in NP time.
My problem is I am not good in theory so it doesn't help me much to talk about the Cook-Levin Theorem or Non-Deterministic Turing Machines.
What I would like is an explanation of the pseudo-polynomial time dynamic programming subset sum that on Wikipedia.
I have read it and I believe I understand the general concept of why it is NP instead of P (related to the size of the input rather than the operations with it), but I do not understand the algorithm.
I would appreciate if someone would put provide an example with some numbers and how it works. It would help me a lot because it would:
- Give me ideas to improve my future algorithm
- Help me understand intuitively when an algorithm is pseudo-polyonmial instead of NP.