3
$\begingroup$

I have a typical subset sum problem and I'm looking to choose the proper algorithm to solve it, the set contains (around) 1000 elements, and elements are constrained to max 22 bits for now.

I have been looking around and looks like the well known O(2^(n/2)) is not an option, and looking into the Dynamic Programming version memory becomes a big concern, because the elements values are pretty balanced

n=1000 s=962,425,151 (Avg=964,452)

Array required: [1000,964452152] = 964,452,152,000 bytes

Even using a bit array, (given I'm estimating the algorithm requirements properly), it will require 112 GB of memory... (964,452,152,000/8 = 120,556,519,000 bytes)

Is there other known subset sum algorithm I could evaluate?

Edit 1: (after Tom reply)

I didn't clarify this in the question:

  • It must be an exact algorithm (not approximate solutions)
  • Should be able to output the subset solving s
$\endgroup$
3
  • 1
    $\begingroup$ Memory is not a real problem, it would take forever for calculation. $\endgroup$
    – rus9384
    Commented Oct 2, 2017 at 18:08
  • $\begingroup$ @rus9384 The dynamic program requires solving roughly $10^{12}$ subproblem instances, and each subproblem can be solved by taking the binary OR of two subproblems. Modern CPUs can do on the order of $10^9$ operations per second; 1000 seconds hardly equals "forever". $\endgroup$ Commented Oct 2, 2017 at 20:11
  • $\begingroup$ @TomvanderZanden, ah, correct, just 4KB. $\endgroup$
    – rus9384
    Commented Oct 2, 2017 at 21:16

1 Answer 1

2
$\begingroup$

You can implement the dynamic programming algorithm using a much smaller amount of memory. You don't need the entire table in memory all the time.

The point is that to answer the question "Is there a set of items $1,\ldots,i$ that sums to $s$?", you only need the answers for $i-1$ (the previous "row" in the DP table), but you don't care about the (previously computed) answers for $i-2,i-3,\ldots$. Thus, at any given time, you'd only need an two arrays of around 120MB each in memory (and in fact, you can do it using only one array!).

However, reconstructing the solution becomes more difficult, since traditionally you'd reconstruct the solution by backtracking through all of the stored values. There's a nice workaround: with each (feasible) subproblem, store how much of the weight is taken up by the first $n/2$ elements.

We can do this computation in time $O(ns)$ (where $s$ is the sum of all elements). From the final row of the dynamic programming table, we can now find not only whether the problem has a solution at all, but also (if a solution exists), what portion of the target sum is achieved by the first $n/2$ elements (and consequently, we also know what portion of the sum the remaining elements make up). We can now solve the two subproblems recursively, each of half size. The total time taken is only $O(ns \log n)$, i.e., we only take a factor $O(\log n)$ hit in the running time for a linear reduction in memory usage.

You should also consider the possibility that perhaps not all possible values can be attained as sum of items in your set. So, depending on the input, perhaps not using a contiguous array of bits, but using instead for example a hash table will use less memory.

Finally (as an alternative solution), if you only need an approximation, consider rounding the values (e.g. to the nearest thousand) to reduce the size of the tables further.

$\endgroup$
4
  • $\begingroup$ thanks for your reply, I was not clear on the question and provided additional details (exact algorithm/must be able to reconstruct the subset), I see there is a chance of improvement on memory terms to find is the subset has a solution, I'll try to analyze what additional memory/processing cost will take to follow the approach you mention, however, as you know how it should be done, could you provide an estimate on the additional cost? thanks $\endgroup$ Commented Oct 2, 2017 at 17:57
  • $\begingroup$ An upper bound of $ns\log_2 n$ is $1000\cdot2^{22}\cdot1000\cdot10=4\cdot10^{13}$. It is bigger than $10^{12}$ estimation. Then another question is a constant under big O notation. $\endgroup$
    – rus9384
    Commented Oct 2, 2017 at 20:29
  • $\begingroup$ @rus9384 The $10^{12}$ estimation is for the original algorithm. Even then, $4\cdot 10^{13}$ operations would only take 11 hours on a 1GHz CPU. Even if the constant factor is relatively bad (I expect it will be pretty good, considering how simple the DP is), the computation could still be done within a week/month. It's well within the realm of possibility. $\endgroup$ Commented Oct 2, 2017 at 21:07
  • $\begingroup$ @Tom van der Zanden thank you for all the insights, I was hoping there was a way to solve this in 'hours' instead of days/weeks, so the DP part is 'fast' but reconstructing the solution will take a while to say the least. $\endgroup$ Commented Oct 3, 2017 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.