how many combinations in a list equal a certain total

[Sherrie]

I have a list of 479 rows. Column A is a product name, column B is cost. I
need to come up with every possible combination of pruducts that equals
$100.

For instance:
Product A $100
Product B $50
Product C $38.72
Product D $20
Product E $30
Product F $50

Possible answers are:
A
B+D+E
B+F
F+E+D

Each Product can be used only once so B+B wouldn't work.

PLEASE PLEASE PLEASE help!

Sherrie

 

[Jim]

Go to www.myweb.cableone.net/twodays
Download the "Find a numeric value" file.

 

[Tom Ogilvy]

Note that that will find one combination - not all combinations (unless the
file has been changed recently).

 

[Jim]

The file will find *one* solution, which may not be the first or the best
and the solution cannot be narrowed by applying criteria. It is a really
simple file that is one possible solution.

 

[Tom Ogilvy]

There are 2^480 - 1 unique combinations to check. As a point of
comparison, there are only 8,640,000 seconds in 100 years (slightly larger
then 2^23) In otherwords, there isn't enough time to do an exhaustive
examination without even trying to look at the results.

You could come up with a list of Unique prices and reduce the number of rows
you need to examine. (so in your example, any solution that contains a B
could be another solution by replacing B with F)

Regards,
Tom Ogilvy

 

[Sherrie]

Is it possible to find ALL solutions? I'd need to be able to do that on a
daily basis for a list of 10 items.

 

[Jim]

Actually, there are quite a few more than 8,640,000 seconds in a hundred
years, but who's counting?! <g>
60 seconds per minute, 60 minutes per hour, 24 hours per day, 365 (or so)
days per year.
=60*60*24*365*100

 

[Myrna Larson]

I don't think it's feasible to solve this problem. There are just too many combinations that
would have to be checked: just considering combinations of 1 to 4 items, there are more than
2.18 billion!

Why do you or your boss think this must be done? Maybe there's a *feasible* solution to your
problem.

 

[Tom Ogilvy]

Damn, your right, I left out the 365 in my formula (doh) - none the less,
there still isn't enough time - but isn't life so much like that <g>

 

[Harlan Grove]

There are 2^480 - 1 unique combinations to check. As a point of
comparison, there are only 8,640,000 seconds in 100 years (slightly larger
then 2^23) . . .

Quibbles.

With 479 items, there are 2^479-1 combinations to check.

8,640,000 secons is 100 days, not years.

. . . In otherwords, there isn't enough time to do an exhaustive
examination without even trying to look at the results.

You could come up with a list of Unique prices and reduce the number of rows
you need to examine. (so in your example, any solution that contains a B
could be another solution by replacing B with F)

Add to those heuristics throwing out all individual items with prices over $100.
Also, for k = INT(100/MIN(PriceList)), k gives the largest cardinality
combinations that need to be checked. That means only 479 choose k combinations
to check. Still, this type of problem lacks practical means to achieve a
comprehensive solution.

 

[Tom Ogilvy]

Quibbles.

With 479 items, there are 2^479-1 combinations to check.

Yes, don't know what I was thinking - thanks for the correction

8,640,000 secons is 100 days, not years.

Already admitted to that one

Have to think about your maximum combinations assertion - (not questioning
it) - thanks