Combination Generator

[Scott Dudley]

I need an algorithm that will, provided a set of decimal numbers,
identify any combination thereof that add up to N. The size of the set
(array, list, etc.) is unknown.

Seems I recall seeing code for a combination generator in one of my
algorithm books (Sedgwick?) that would fit the bill. Unfortunately, I'm
faced with a challenge at work and my books are at home.

Thanks.

 

[Roedy Green]

Seems I recall seeing code for a combination generator in one of my
algorithm books (Sedgwick?) that would fit the bill. Unfortunately, I'm
faced with a challenge at work and my books are at home.

see http://mindprod.com/jgloss/combination.html

--
Bush crime family lost/embezzled $3 trillion from Pentagon.
Complicit Bush-friendly media keeps mum. Rumsfeld confesses on video.
http://www.infowars.com/articles/us/mckinney_grills_rumsfeld.htm

Canadian Mind Products, Roedy Green.
See http://mindprod.com/iraq.html photos of Bush's war crimes

 

[Gordon Beaton]

I need an algorithm that will, provided a set of decimal numbers,
identify any combination thereof that add up to N. The size of the
set (array, list, etc.) is unknown.

This is a knapsack problem, a one-dimensional special case of bin
packing. You'll find lots of information, analysis and example code if
you google. AFAIK the problem is NP-complete.

Here's a good heuristic however, from memory:

Choose the largest of your remaining elements that fits in N, and
reduce N accordingly. Repeat until either N is 0, or there are no more
elements that are small enough.

/gordon

 

[bugbear]

I need an algorithm that will, provided a set of decimal numbers,
identify any combination thereof that add up to N. The size of the set
(array, list, etc.) is unknown.

Seems I recall seeing code for a combination generator in one of my
algorithm books (Sedgwick?) that would fit the bill. Unfortunately, I'm
faced with a challenge at work and my books are at home.

http://www.nuigalway.ie/mat/algorithms/knapsack.html

BugBear