how many combinations in a list equal a certain total?

  • Thread starter Thread starter Sherrie
  • Start date Start date
S

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
 
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.
Click to expand...

Strictly speaking, that means that you'll have to check every single
one of the 479 factorial (479!) possible combinations; that comes to
3.9173045820870296921477280441711e+1077 tests. The fastest
supercomputer in the world couldn't do it before the sun burns out!

Ok, you can cut the problem down, but I don't think a query solution
will work. The "Greedy Algorithm" could be implemented in VBA - pick
the largest cost under $100, then the largest cost less than the
balance, and so on; but it's still going to be a hideously slow
process, and the time will scale exponentially with the number of
records.

Good luck... you'll need it!
 
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.
Click to expand...

Another followup, after thinking about this.

Suppose that all 479 prices were $1.00 (you found a good deal at your
local Honk's Only A Dollar Store). This would give you 479!/(479 -
100)! = 1.5769952075846390721537858713197e+263 valid answers. Better
stock up on LOTS of paper (a stack from here to Mars) to print out
your result set...

Basically, I would say that the problem will generate a combinatorial
explosion no matter how you slice it, and is essentially just a Badly
Phrased Problem that has no practical solution.
 
Back
Top