Re: Summing numbers from a list to a goal

Paul E. Black <p.black@xxxxxxx> wrote:
On Monday 30 June 2008 13:37, jeffbg123 wrote:
I am trying to figure out the quickest way to do the following.

You are given a list of integers, a goal sum (integer), and an
acceptable +/- (integer).

The goal is to find a list of integers, all from the first list (all
unique) that sum up to the goal sum plus or minus the acceptable
range.

Example:

list: 1,2,3,4,5,6,7,8,9
Goal: 8
+/-: 1

It would output one of the following, whichever it found first:
1,2,4
1,3,4
1,6
1,7
.......etc

Basically whatever numbers sum to 7,8, or 9

Is there a quick way of doing this?

Not without additional constraints.

Notably faster than brute force?

Yes. Split your numbers in half arbitrarily. Find all subset sums of
each half independently. Sort the lists of subset sums. Now you have
two (huge) sorted lists of subset sums, and you can find out whether
there is an acceptable subset sum in time linear in the length of the
lists. This takes O(sqrt(2)^n) space and O(n sqrt(2)^n) time ---
considerably faster than brute force's O(2^n) time.

In practice, this algorithm still sucks. A better approach is based on
integer programming --- you write a single integer program whose
feasible region defines the set of subsets that sum to something you
care about, then you solve it using branch-and-bound and a hell of a lot
of cutting planes.

No, the problem is often called "subset sum", and it is a classic hard
(NP) problem.

Not all problems in NP are hard. "Given three integers in binary,
decide whether the third integer is the sum of the first two" is quite
easy to solve, yet is still in NP.

There are many heuristics that can speed up some cases: sort the input
list, dynamic programming, memozing, etc.

The classic dynamic programming solution will work if your "integers"
are in fact *small* integers.
.

Relevant Pages

  • Re: abundance of irrationals!)
    ... No such "sum" exists except as, and only as, the limit of the infinite ... If an infinite sequence does not have to "achieve" its limit, ... > It is only for lists not initially known not to be surjective that ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... Not in that sum which stretches over all n. ... It is only for lists not initially known not to be surjective that ... "infinite" sequence. ... you cannot enumerate by them. ...
    (sci.math)
  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Simple recursive functions in Lisp
    ... (defun sum (list) ... (loop for x in list sum x)) ... Why is loop disqualified as "higher level"? ... use a macro such as RECURSE that has the same knowledge of lists and ...
    (comp.lang.lisp)
  • Re: Summing numbers from a list to a goal
    ... unique) that sum up to the goal sum plus or minus the acceptable ... Sort the lists of subset sums. ...
    (comp.programming.contests)
Loading