Post date: Jul 16, 2014 12:30:48 AM
"How many ways are there to make 2 pounds sterling using the 8 coins 1p, 2p, 5p, 10p, 20p, 50p, 100p, and 200p?"
This is done in the same way I sometimes build tables of integers, except that the bases are different. The key to performance, however, is realizing that we don't need to include 1p coins. We know that anything under 200 can be padded with 1p coins to make 200p, so we can just compare less than/equal and assume the inclusion of 1p coins. The means the number of rows being counted is 1/200 as many.
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 100
)
INSERT INTO #Integers
SELECT i
FROM Integers
SELECT COUNT(*)
FROM #Integers p2
CROSS JOIN #Integers p5
CROSS JOIN #Integers p10
CROSS JOIN #Integers p20
CROSS JOIN #Integers p50
CROSS JOIN #Integers L
CROSS JOIN #Integers L2
WHERE -- Calculate combinations.
2 * p2.i
+ 5 * p5.i
+ 10 * p10.i
+ 20 * p20.i
+ 50 * p50.i
+ 100 * L.i
+ 200 * L2.i <= 200
-- We know that certain quantities are impossible because the total would be too high. Make this faster by filtering them out.
AND L2.i <= 1
AND L.i <= 2
AND p50.i <= 4
AND p20.i <= 10
AND p10.i <= 20
AND p5.i <= 40
DROP TABLE #Integers