Subset sum Problem

by

I’m not quite sure if your solution is exact or a PTA (poly-time approximation).

But, as someone pointed out, this problem is indeed NP-Complete.

Meaning, every known (exact) algorithm has an exponential time behavior on the size of the input.

Meaning, if you can process 1 operation in .01 nanosecond then, for a list of 59 elements it’ll take:

2^59 ops -->     2^59     seconds -->     2^26      years -->      1 year
            --------------           ---------------
            10.000.000.000           3600 x 24 x 365

You can find heuristics, which give you just a CHANCE of finding an exact solution in polynomial time.

On the other side, if you restrict the problem (to another) using bounds for the values of the numbers in the set, then the problem complexity reduces to polynomial time. But even then the memory space consumed will be a polynomial of VERY High Order.
The memory consumed will be much larger than the few gigabytes you have in memory.
And even much larger than the few tera-bytes on your hard drive.

( That’s for small values of the bound for the value of the elements in the set )

May be this is the case of your Dynamic programing algorithm.

It seemed to me that you were using a bound of 1000 when building your initialization matrix.

You can try a smaller bound. That is… if your input is consistently consist of small values.

Good Luck!

More Related Contents:

  1. Find all combinations of a list of numbers with a given sum
  2. How do i implement these algorithms below
  3. Removing duplicates in lists
  4. How to generate all permutations of a list?
  5. How to efficiently compare two unordered lists (not sets) in Python?
  6. How to split text without spaces into list of words
  7. Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraint
  8. Weighted random selection with and without replacement
  9. What is the fastest way to flatten arbitrarily nested lists in Python? [duplicate]
  10. Understanding recursion in Python
  11. Efficient calculation of Fibonacci series
  12. How did Python implement the built-in function pow()?
  13. Find longest repetitive sequence in a string
  14. Python string ‘in’ operator implementation algorithm and time complexity
  15. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  16. Checking if all elements in a list are unique
  17. Mapping a range of values to another
  18. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  19. Weighted random sample in python
  20. How to check whether two lists are circularly identical in Python
  21. How to test if one string is a subsequence of another? [duplicate]
  22. Fast prime factorization module
  23. What’s the algorithm of ‘set.intersection()’ in python?
  24. How to incrementally sample without replacement?
  25. Replace list of list with “condensed” list of list while maintaining order
  26. Python Weighted Random [duplicate]
  27. How can I interleave or create unique permutations of two strings (without recursion)
  28. Python: powerset of a given set with generators [duplicate]
  29. What is the Big O Complexity of Reversing the Order of Columns in Pandas DataFrame?
  30. Getting the subsets of a set in Python

Leave a Comment