Peter Larsson Blog

Patron Saint of Lost Yaks

Bin packaging

by Peter Larsson in  , , ,

With respect to my old algorithm found here http://weblogs.sqlteam.com/peterl/archive/2008/08/12/How-to-sum-up-an-unknown-number-of-records.aspx which is about how to sum up an unknown number of items, I have come up with a new algorithm.
 
This new algorithm is about finding all possible sums and how many combinations you have of each sum.
Have fun!
 
DECLARE       @Data TABLE
       (
              faceValue MONEY,
              maxItems INT,
              permCount INT
       )

INSERT        @Data
              (
                     faceValue,
                     maxItems
              )
SELECT        faceValue,
              1 + COUNT(*)
FROM          (
                     SELECT 899 AS faceValue UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 95 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 55 UNION ALL
                     SELECT 40 UNION ALL
                     SELECT 5 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 250 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 90 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 350 UNION ALL
                     SELECT 450 UNION ALL
                     SELECT 450 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 100 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 50 UNION ALL
                     SELECT 1 UNION ALL
                     SELECT 10 UNION ALL
                     SELECT 1
              ) AS d
GROUP BY      faceValue

DECLARE       @comb INT

UPDATE @Data
SET    @comb = permCount = maxItems * COALESCE(@comb, 1)

SELECT        theSum,
              COUNT(*) AS theCount
FROM          (
                     SELECT        SUM(d.faceValue *((v.number * d.maxItems / d.permCount) % d.maxItems)) AS theSum
                     FROM          @Data AS d
                     INNER JOIN    TallyNumbers AS v ON v.number <= @comb
                     GROUP BY      v.number
                     HAVING        SUM(d.faceValue *((v.number * d.maxItems / d.permCount) % d.maxItems)) > 0
              ) AS d
GROUP BY      theSum
ORDER BY      COUNT(*) DESC,
              theSum

Now you can see for any possible sum how many combination you have to get that sum.
With the sample data provided above, you can see that you can get the sum of 2651 rupees in 966 different ways, but you can only get the sum of 1019 rupees in one way.

 

Legacy Comments
Cameron
2009-02-25		 re: Bin packaging
I'm trying to figure out what you're doing here. I populate Tally Numbers with 1019 and 2651, the script returns

theSum theCount
--------------------- -----------
202.00 1
1821.00 1

I'm pretty sure I'm missing something.