Re: Help with an algorithm to do the following:


On Sun, 10 Apr 2005, fadi wrote: 

I have 1 item that has 3 categories (numerical values). I need to find the
right combination to get a matching desired total for all 3. For example:

Item1 | 60 | 40 | 10
Item2 | 100 | 0 | 7
Item3 | 10 | 50 | 13
Item4 | 0 | 10 | 4

If I am looking for: 420 | 100 | 54 then I would get the following matching:

4 Item2
2 Item3

What would be the best approach?

This kind of problem is called "linear programming," and there are well-known ways to solve it. Basically, you have some linear equations

  60x + 100y + 10z +  0w = 420
  40x +   0y + 50z + 10w = 100
  10x +   7y + 13z +  4w =  54

and you want to solve them for x,y,z,w. One way of solving linear constraints like this requires some knowledge of computational geometry.
I don't have any experience with solving LP problems above dimension 2
(which would be problems where you're solving only for 'x' and 'y', instead of four different variables), but the same kinds of algorithms
probably apply.

  You implied you wanted solutions where x,y,z,w were all non-negative
integers --- no fractions or negative numbers. If this is the case, I
bet a Google search specifically for "discrete" linear programming would
turn up some useful information.

HTH,
-Arthur
.