A few days ago on CF-Talk Greg Morphis asked for a method to find the cheapest combination of phone plans that satisfy a customer's requirements for the number of lines being used and the amount of minutes to share between the plans. At first, I thought the answer could be derived directly, but since the plans and their relative price/minute values are essentially random, they create different price breaks that change as you add minutes and lines. This means one combination of plans might be the cheapest for 500 minutes, but once you increase that to 600 minutes, a completely different set of plans might come into play that are now the cheapest.I offered a brute force method would mean calculating ALL POSSIBLE combination of plans and lines and then taking the cheapest one that matches the criteria. Feeling sightly obliged to explain the process, and growing continuously more curious abut the solution I pulled together a proof of concept. I will not promise that this is the fastest nor the best solution, but it does work. Here is the setup. The poster gave 9 sample phone plans with a known price and number of minutes to choose from to create the customer's package:
  • PLAN A $25.00, 0 minutes
  • PLAN B $32.00, 200 minutes
  • PLAN C $42.00, 500 minutes
  • PLAN D $52.00, 750 minutes
  • PLAN E $63.00, 900 minutes
  • PLAN F $84.00, 1,400 minutes
  • PLAN G $105.00, 2,100 minutes
  • PLAN H $155.00, 4,000 minutes
  • PLAN I $210.00, 6,000 minutes
The input parameters would simply be the number of phone lines desired by the customer as well as the number of minutes needed to share across the lines. For example. 10 lines 9,500 minutes would be
1 @ PLAN I = 210.00 (6000 minutes)
7 @ PLAN C = 294.00 (3500 minutes)
2 @ PLAN A = 50.00 (0 minutes)
total = 554.00 Assumptions made are that if there are no plans that can be used in combination with the given number of lines to reach the required amount of minutes, nothing will be returned. Also, if the exact number of minutes cannot be reached, the cheapest plan that exceeds the minutes will be given. Given an example requirement of 10 lines, I decided that the output of my code would always come in this form since it would be possible to not use a plan at all, or to use the same plan over and over for all 10 lines: PLAN A 0-10 times
PLAN B 0-10 times
PLAN C 0-10 times
...
PLAN N 0-10 times This means that there are 10+1 possible configurations of each plan. And since we need to find all possible combination of all possible plans configurations, and we have 9 plans, that means all our possible plan combinations looks like this: 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 x 10+1 = 11^9 = 2,357,947,691 That's a lot. If we replace our example of 10 lines with numberOfLines and 9 plans with numberOfPlans, we can generically represent the possibilities as: (numberOfLines+1)^numberOfPlans That's about all the theory I can explain without just showing the code now. I tested this on SQL Server 2000, mostly because I didn't have anything else handy at the time. The reason I decided to try a SQL server solution is because SQL server makes it easy to create a Cartesian Product by joining two tables on an always true statement thus returning a result set that represents every possible combination of all records in both tables. The last time I used this was when I was experimenting with Rainbow Tables and wanted to generate all possible passwords given a set of characters. 
[code]SET NOCOUNT ON

DECLARE @numLines AS int
DECLARE @numMinutes AS int
DECLARE @counter AS int


/* Set Parameters here */
SET @numLines = 10
SET @numMinutes = 9500
/* Set Parameters here */

SET @counter = 1

IF EXISTS (SELECT * FROM tempdb.dbo.sysobjects o WHERE o.xtype in ('U') AND o.id = object_id( N'tempdb..#plans'))
	DROP TABLE #plans
IF EXISTS (SELECT * FROM tempdb.dbo.sysobjects o WHERE o.xtype in ('U') AND o.id = object_id( N'tempdb..#repeats'))
	DROP TABLE #repeats
IF EXISTS (SELECT * FROM tempdb.dbo.sysobjects o WHERE o.xtype in ('U') AND o.id = object_id( N'tempdb..#combinations'))
	DROP TABLE #combinations

CREATE TABLE #plans
(name varchar(10) PRIMARY KEY,
price money,
minutes int,
processed bit DEFAULT 0)

CREATE TABLE #repeats
(repeat int PRIMARY KEY)

CREATE TABLE #combinations
(planName varchar(10),
repeat int,
minutes int,
price money)

CREATE CLUSTERED INDEX #combo_plan_name ON #combinations (planName)


INSERT INTO #plans (name, price, minutes)
SELECT 'PLANA', 25.00, 0
UNION SELECT 'PLANB', 32.00, 200
UNION SELECT 'PLANC', 42.00, 500
UNION SELECT 'PLAND', 52.00, 750
UNION SELECT 'PLANE', 63.00, 900
UNION SELECT 'PLANF', 84.00, 1400
UNION SELECT 'PLANG', 105.00, 2100
UNION SELECT 'PLANH', 155.00, 4000
UNION SELECT 'PLANI', 210.00, 6000

SET @counter = 0
WHILE @counter <= @numLines
BEGIN
	INSERT INTO #repeats VALUES (@counter)
	SET @counter = @counter + 1
END

INSERT INTO #combinations (planName, repeat, minutes, price)
SELECT p.name, r.repeat, p.minutes * r.repeat as minutes, p.price * r.repeat as price
FROM #plans p
INNER JOIN #repeats r ON 1 = 1

SELECT TOP 1 a.repeat AS 'PlanA',
	b.repeat AS 'PlanB',
	c.repeat AS 'PlanC',
	d.repeat AS 'PlanD',
	e.repeat AS 'PlanE',
	f.repeat AS 'PlanF',
	g.repeat AS 'PlanG',
	h.repeat AS 'PlanH',
	i.repeat AS 'PlanI',
	a.price + b.price + c.price + d.price + e.price + f.price + g.price + h.price + i.price AS price,
	a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes + h.minutes + i.minutes AS minutes
FROM #combinations a
INNER JOIN #combinations b ON b.planName = 'PlanB'
	AND a.repeat + b.repeat <= @numLines
	AND a.minutes + b.minutes < @numMinutes + 100
INNER JOIN #combinations c ON c.planName = 'PlanC'
	AND a.repeat + b.repeat + c.repeat <= @numLines
	AND a.minutes + b.minutes + c.minutes < @numMinutes + 500
INNER JOIN #combinations d ON d.planName = 'PlanD'
	AND a.repeat + b.repeat + c.repeat + d.repeat <= @numLines
	AND a.minutes + b.minutes + c.minutes + d.minutes < @numMinutes + 500
INNER JOIN #combinations e ON e.planName = 'PlanE'
	AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat <= @numLines
	AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes < @numMinutes + 500
INNER JOIN #combinations f ON f.planName = 'PlanF'
	AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat <= @numLines
	AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes < @numMinutes + 500
INNER JOIN #combinations g ON g.planName = 'PlanG'
	AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat + g.repeat <= @numLines
	AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes < @numMinutes + 500
INNER JOIN #combinations h ON h.planName = 'PlanH'
	AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat + g.repeat + h.repeat <= @numLines
	AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes + h.minutes < @numMinutes + 500
INNER JOIN #combinations i ON i.planName = 'PlanI'
	AND a.repeat + b.repeat + c.repeat + d.repeat + e.repeat + f.repeat + g.repeat + h.repeat + i.repeat = @numLines
	AND a.minutes + b.minutes + c.minutes + d.minutes + e.minutes + f.minutes + g.minutes + h.minutes + i.minutes >= @numMinutes
WHERE a.planName = 'PlanA'
ORDER BY a.price + b.price + c.price + d.price + e.price + f.price + g.price + h.price + i.price
[/code]
What this code essentially does is populates a temp table full of plans, another temp table with numbers 1 through the number of lines to represent how many times each plan MIGHT be repeated. Those tables are joined into a Cartesian product that shows the possible number of times each plan might be used. The resulting table of combinations is joined together once for each plan to generate all the possible plan combinations. Note the redundant AND statements in each join. If I wanted, I could have just limited my result set once at the end, but you'll remember that our example of 10 lines and 9500 minutes has over 2 Billion combinations. Filtering down the result set as we build the combinations eliminates combinations that we know aren't going to work and there's no use keeping them around the result set any longer. This has a phenomenal increase in performance since it keeps the growth more linear than exponential. With this method, the final WHERE clause is only applied to 233,288 records. (I cheated and looked at the execution plan for this number) Performance on my SQL Server 2000 box is about 1 second to calculate the 10 lines, 9,500 minutes example. It absolutely flies when you do something simple like 3 lines 1,000 minutes. I would definitely want to put a cap on it though. I believe it took about five minute to calculate 30 lines and 20,000 minutes. The numbers just start getting silly huge if you go crazy with it. Now, one last thing. The number of plans could change at any time-- A plan could be added or removed. I gave the first bit of code with the final select hard-coded for readability. SQL is butt-ugly at making dynamic queries, but if you replace the final select with the following code, it will be dynamic based on how many plans there are. Frankly I recommend you do the dynamic part in CF and output it in a cfquery, but here's the SQL-only version: 
[code]
DECLARE @planNameCounter varchar(20)
DECLARE @SQLPriceAdd AS varchar(8000)
DECLARE @SQLRepeatAdd AS varchar(8000)
DECLARE @SQLMinutesAdd AS varchar(8000)
DECLARE @SQLRepeatColumns AS varchar(8000)
DECLARE @SQLWhere AS varchar(500)
DECLARE @SQLJoins AS varchar(8000)
DECLARE @SQLTotal AS varchar(8000)
DECLARE @position AS varchar(20)
SELECT @SQLPriceAdd = '', @SQLMinutesAdd = '', @SQLRepeatColumns = '', @SQLRepeatAdd = '', @SQLJoins = '', @position = 'FIRST', @SQLWhere = ''

WHILE EXISTS(SELECT 1 FROM #plans WHERE processed = 0)
BEGIN
	SELECT  TOP 1 @planNameCounter = name,
		@SQLRepeatColumns = @SQLRepeatColumns + '
			' + name + '.repeat AS ''' + name + ''',',
		@SQLMinutesAdd = @SQLMinutesAdd + CASE WHEN @position <> 'FIRST' THEN ' + ' ELSE '' END + name + '.minutes',
		@SQLPriceAdd = @SQLPriceAdd + CASE WHEN @position <> 'FIRST' THEN ' + ' ELSE '' END + name + '.price',
		@SQLRepeatAdd = @SQLRepeatAdd + CASE WHEN @position <> 'FIRST' THEN ' + ' ELSE '' END + name + '.repeat',
		@SQLJoins = @SQLJoins + CASE WHEN @position = 'FIRST' THEN '
			FROM #combinations ' + name ELSE '
			INNER JOIN #combinations ' + name + ' ON ' + name + '.planName = ''' + name + '''
				AND ' + @SQLRepeatAdd + CASE WHEN @position = 'LAST' THEN ' = ' ELSE ' <= ' END + cast(@numLines as varchar(10)) + '
				AND ' + @SQLMinutesAdd + CASE WHEN @position = 'LAST' THEN ' >= ' + cast(@numMinutes as varchar(10)) ELSE ' < ' + cast(@numMinutes + 100 as varchar(10)) END END,
		@SQLWhere = CASE WHEN @position = 'FIRST' THEN 'WHERE ' + name + '.planName = ''' + name + '''' ELSE @SQLWhere END		
	FROM #plans
	WHERE processed = 0
	ORDER BY name

	UPDATE #plans
	SET processed = 1
	WHERE name = @planNameCounter

	SELECT @position = CASE WHEN count(1) = 1 THEN 'LAST' ELSE 'MIDDLE' END
	FROM #plans WHERE processed = 0	
	
END

SET @SQLTotal = '			SELECT TOP 1 ' + @SQLRepeatColumns +'
			' + @SQLPriceAdd + ' AS price,' + '
			' + @SQLMinutesAdd + ' AS minutes' + @SQLJoins + '
			' + @SQLWhere + '
			ORDER BY ' + @SQLPriceAdd


EXEC (@SQLTotal)
[/code]
Well, there you have it. I hope this is useful to the original poster, and at least entertaining for the rest of you. Let me know you have any questions or suggestions. I whipped most of this up late at night, so I'm sure there's some tweaking that could still be done.