A Christmas Teaser - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2005 Forums

Transact-SQL (2005)

A Christmas Teaser

Author

Topic

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-12-16 : 08:53:40

Slow day in the office and, while looking in my wallet I was struck by a strange idea....

Given a table of coinage (a number of £1, 50p, 20p... etc) coins and a target amount. How easy would it be to write an algorithm in SQL to determine if the target is reachable and the minimum number of coins needed to get there?

For example say you have


3 pennies
1 two pence piece
1 five pence piece
2 twenty pence pieces
1 fifty pence piece
and 2 pound coins

Is it possible to exactly get £1.93 with that set of coins and, if so, what's the minimum number of coins you need to do it.

(for the above it is possible and the minimum number of required coins is 7 : 1 * £1, 1 * 50p, 2 * 20p, 3 * 1p )

My method (at the end of the post) uses a greedy algorithm and I'm sure there must be many more efficient ways to do the job. (I thought there might be a way using the quirky updates but I can't get my head around them).

Here's how to get the sample data. It uses F_TABLE_NUMBER_RANGE which you probably already have but I'll post it anyway


CREATE FUNCTION [dbo].[F_TABLE_NUMBER_RANGE]
(
	@startNumber INT
	, @endNumber INT
)
RETURNS TABLE AS RETURN
(
WITH powers AS (
	SELECT
		[N01], [N02], [N03]
	FROM
		(
			SELECT [N01] =  0 UNION SELECT    1 UNION SELECT    2 UNION SELECT    3
			UNION SELECT    4 UNION SELECT    5 UNION SELECT    6 UNION SELECT    7
			UNION SELECT    8 UNION SELECT    9 UNION SELECT   10 UNION SELECT   11
			UNION SELECT   12 UNION SELECT   13 UNION SELECT   14 UNION SELECT   15
		) NO1

		CROSS JOIN (
			SELECT [N02] =  0 UNION SELECT   16 UNION SELECT   32 UNION SELECT   48
			UNION SELECT   64 UNION SELECT   80 UNION SELECT   96 UNION SELECT  112
			UNION SELECT  128 UNION SELECT  144 UNION SELECT  160 UNION SELECT  176
			UNION SELECT  192 UNION SELECT  208 UNION SELECT  224 UNION SELECT  240
		) NO2

		CROSS JOIN (
			SELECT [N03] =  0 UNION SELECT  256 UNION SELECT  512 UNION SELECT  768
			UNION SELECT 1024 UNION SELECT 1280 UNION SELECT 1536 UNION SELECT 1792
			UNION SELECT 2048 UNION SELECT 2304 UNION SELECT 2560 UNION SELECT 2816
			UNION SELECT 3072 UNION SELECT 3328 UNION SELECT 3584 UNION SELECT 3840
		) N03
	)
SELECT TOP 100 PERCENT
	[number] = ( a.[number] + b.[number] ) + CASE WHEN @startNumber <= @endNumber THEN @startNumber ELSE @endNumber END
FROM
	(
		SELECT TOP 100 PERCENT
			[number] = CAST([N01] + [N02] + [N03] AS INT)
		FROM
			powers
		WHERE
			[N01] + [N02] + [N03] < CAST(CEILING(SQRT(ABS(@startNumber - @endNumber) + 1 )) AS INT)
		ORDER BY
			1
	) a
	CROSS JOIN (
		SELECT TOP 100 PERCENT
			[number] =  CAST(([N01] + [N02] + [N03]) * CAST(CEILING(SQRT(ABS(@startNumber - @endNumber) + 1 )) AS INT) AS INT)
		FROM 
			powers
		WHERE
			[N01] + [N02] + [N03] < CAST(CEILING(SQRT(ABS(@startNumber - @endNumber) + 1 )) AS INT)
		ORDER BY
			1
	) b
WHERE
	a.[number] + b.[number] < ABS(@startNumber - @endNumber) + 1
	AND (16777216 - ABS( @startNumber - @endNumber ) - 1 ) > 0
ORDER BY
	1
)
GO

And here's the sample data set. (currently at 100,000 rows)


-- Populate Data
IF OBJECT_ID('tempDb..#problem') IS NOT NULL DROP TABLE #problem
SELECT
	[number] AS [RowNo]
	, ABS(CAST(HASHBYTES('md5', CAST([number] AS VARCHAR(6))) AS INT)) % 10 AS [1p]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 10000 AS VARCHAR(6))) AS INT)) % 5 AS [2p]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 20000 AS VARCHAR(6))) AS INT)) % 6 AS [5p]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 30000 AS VARCHAR(6))) AS INT)) % 10 AS [10p]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 40000 AS VARCHAR(6))) AS INT)) % 8 AS [20p]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 50000 AS VARCHAR(6))) AS INT)) % 8 AS [50p]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 60000 AS VARCHAR(6))) AS INT)) % 3 AS [1UKP]
	, ABS(CAST(HASHBYTES('md5', CAST([number] + 70000 AS VARCHAR(6))) AS INT)) % 500 AS [Target]
INTO
	#problem
FROM
	DBO.F_TABLE_NUMBER_RANGE(1,100000)
ORDER BY
	[number]

And here's the horrible code I threw together to work this out using a greedy algorthm.


DECLARE @level INT                          
DECLARE @rowcount INT

-- Data Structure
IF OBJECT_ID('tempDb..#matrix') IS NOT NULL DROP TABLE #matrix
SELECT
	[rowNo] AS [rowNo]
	, [target] AS [target]
	, 0 AS [cur_Value]
	, 0 AS [cur_CoinCount]
	, [1UKP] AS [100]
	, [50p] AS [50]
	, [20p] AS [20]
	, [10p] AS [10]
	, [5p] AS [5]
	, [2p] AS [2]
	, [1p] AS [1]
	, CAST(NULL AS INT) AS [pos]
	, CAST(NULL AS INT) AS [fewest]
INTO
	#matrix
FROM
	#problem

CREATE CLUSTERED INDEX IX_COINS ON #matrix ([100], [50], [20], [10], [5], [2], [1])


-- First of all elimate any rows where there are just not enough coins
UPDATE m SET
	[pos] = 0
FROM
	#matrix m
	JOIN (
		SELECT
			[rowNo]
			,
				  100 * SUM([100])
				+ 50 * SUM([50])
				+ 20 * SUM([20])
				+ 10 * SUM([10])
				+ 5 * SUM([5])
				+ 2 * SUM([2])
				+ SUM([1])
			AS [Maximum]
		FROM
			#matrix
		GROUP BY
			[rowNo]
		)
		m2 ON m2.[rowNo] = m.[rowNo]
WHERE
	m2.[maximum] < m.[target]
SELECT @@ROWCOUNT

SET @level = 0
WHILE @level < 7 BEGIN

	SET @rowCount = 1

	WHILE @rowCount > 0 BEGIN

		UPDATE #matrix SET
			[cur_Value] = CASE 
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN [cur_Value] + 100
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN [cur_Value] + 50
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN [cur_Value] + 20
				WHEN [target] - [cur_Value] >= 10 AND [10] > 0 THEN [cur_Value] + 10
				WHEN [target] - [cur_Value] >= 5 AND [5] > 0 THEN [cur_Value] + 5
				WHEN [target] - [cur_Value] >= 2 AND [2] > 0 THEN [cur_Value] + 2
				WHEN [target] - [cur_Value] >= 1 AND [1] > 0 THEN [cur_Value] + 1
				ELSE [cur_Value]
			END

			, [cur_coinCount] = CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN [cur_coinCount] + 1
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN [cur_coinCount] + 1
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN [cur_coinCount] + 1
				WHEN [target] - [cur_Value] >= 10 AND [10] > 0 THEN [cur_coinCount] + 1
				WHEN [target] - [cur_Value] >= 5 AND [5] > 0 THEN [cur_coinCount] + 1
				WHEN [target] - [cur_Value] >= 2 AND [2] > 0 THEN [cur_coinCount] + 1
				WHEN [target] - [cur_Value] >= 1 AND [1] > 0 THEN [cur_coinCount] + 1
				ELSE [cur_CoinCount]
			END

			, [100] = [100] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 1
				ELSE [100]
			END

			, [50] = [50] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN 1
				ELSE [50]
			END

			, [20] = [20] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN 1
				ELSE [20]
			END

			, [10] = [10] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 10 AND [10] > 0 THEN 1
				ELSE [10]
			END

			, [5] = [5] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 10 AND [10] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 5 AND [5] > 0 THEN 1
				ELSE [5]
			END

			, [2] = [2] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 10 AND [10] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 5 AND [5] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 2 AND [2] > 0 THEN 1
				ELSE [2]
			END

			, [1] = [1] - CASE
				WHEN [target] - [cur_Value] >= 100 AND [100] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 50 AND [50] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 20 AND [20] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 10 AND [10] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 5 AND [5] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 2 AND [2] > 0 THEN 0
				WHEN [target] - [cur_Value] >= 1 AND [1] > 0 THEN 1
				ELSE [1]
			END
		WHERE
			([pos] IS NULL OR [pos] = 1)

			AND ([fewest] > [cur_CoinCount] + 1 OR [fewest] IS NULL)

			AND ( [100] + [50] + [20] + [10] + [5] + [2] + [1] > 0 )
	
		SELECT @rowCount = @@ROWCOUNT
	END
		
	-- Update found rows
	UPDATE #matrix SET
		[pos] = 1
		, [fewest] = [cur_CoinCount]
	WHERE
		[cur_value] = [target]
		AND [pos] IS NULL

	-- Increment Level
	SET @level = @level + 1

	-- Refresh data
	UPDATE #matrix SET
		[cur_Value] = 0
		, [cur_CoinCount] = 0
		, [100] = CASE WHEN @level > 0 THEN 0 ELSE [1UKP] END
		, [50] = CASE WHEN @level > 1 THEN 0 ELSE [50p] END
		, [20] = CASE WHEN @level > 2 THEN 0 ELSE [20p] END
		, [10] = CASE WHEN @level > 3 THEN 0 ELSE [10p] END
		, [5] = CASE WHEN @level > 4 THEN 0 ELSE [5p] END
		, [2] = CASE WHEN @level > 5 THEN 0 ELSE [2p] END
		, [1] = CASE WHEN @level > 6 THEN 0 ELSE [1p] END
	FROM
		#matrix m
		JOIN #problem p ON p.[rowNo] = m.[rowNo]
END

UPDATE #matrix SET [pos] = 0 WHERE [pos] IS NULL
SELECT @@ROWCOUNT

SELECT
	p.[rowNo]
	, p.[target] AS [target]
	, p.[1UKP] AS [100]
	, p.[50p] AS [50]
	, p.[20p] AS [20]
	, p.[10p] AS [10]
	, p.[5p] AS [5]
	, p.[2p] AS [2]
	, p.[1p] AS [1]
	, m.[pos] AS [Possible]
	, m.[fewest] AS [Fewest No. Of Coins]
FROM
	#problem p
	JOIN #matrix m ON m.[rowNo] = p.[rowNo]

On my woefully slow dev box this takes 5mins, 31seconds for the 100,000 rows. That's a lot of headroom for improvement!

So, any ideas?

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

khtan
In (Som, Ni, Yak)

17689 Posts

Posted - 2009-12-16 : 09:07:59

I recall Peter has something similar on this sometime back.

KH
[spoiler]Time is always against us[/spoiler]

khtan
In (Som, Ni, Yak)

17689 Posts

Posted - 2009-12-16 : 09:16:50

i didn't go through the code . . think should be this
http://weblogs.sqlteam.com/peterl/archive/2008/08/12/How-to-sum-up-an-unknown-number-of-records.aspx

KH
[spoiler]Time is always against us[/spoiler]

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2009-12-17 : 12:39:49

Shame it produces the wrong answer, e.g.


SELECT 1 AS [RowNo]
  , 10 AS [1p]
  , 0 AS [2p]
  , 0 AS [5p]
  , 0 AS [10p]
  , 3 AS [20p]
  , 2 AS [50p]
  , 0 AS [1UKP]
  , 110 AS Target
INTO #problem

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2009-12-17 : 14:11:05

This should now tell you if you could successfully make the amounts from the coins listed.

It is not full proof because if a smaller coin requires multiples and requires you to not use the larger when it's smaller than the total it will fail. For most real scenerios this will accuratly work though.



Declare @Test table(MyOrder int  identity(1,1) Primary Key Clustered , Myvalue decimal(12,4),MyName varchar(20),Cents decimal(10,4),HowMany Decimal(12,4),Passed int, test money)
Insert Into @TEst(MyValue,MyName,Cents)
Select b.MyValue,a.* from
(
select 'Penny'as n,.01 as amount Union all
select 'Nickel',.05 Union all
select 'Dime',.10 Union all
select 'Quarter',.25 Union all
select 'Half Dollar',.50 Union all
select '$1',1.0 Union all
select '$5',5.0 Union all
select '$10',10.0 Union all
select '$20',20.0 Union all
select '$50',50.0 Union all
select '$100',100.0 
) a
Cross Join
(
Select .02 as MyValue Union All 
Select .30 Union All 
Select 4545.334 Union All 
Select 45325.33 as myvalue
) b
order by b.MyValue,a.amount desc


Declare @Ancher as int,@HowMany as Decimal(12,4),@Remaining as decimal(12,4),@Passed Int

Update a
set 
@Remaining = case when a.Cents = 100 then a.Myvalue else @Remaining end
,@HowMany = a.HowMany = case when @Remaining >= a.Cents then floor(@Remaining/a.Cents) else 0 end
,@Remaining = case when @Remaining >= a.Cents then @Remaining - (@HowMany * a.Cents) else @remaining end
,@Passed = a.Passed = case When @Remaining  = 0 then 1 else 0 end
,@Ancher = a.MyOrder
,test = @remaining
from 
@Test a


select b.Passed,a.MyValue,isnull([$100],0) as [$100],isnull([$50],0) as [$50],isnull([$20],0)as [$20],isnull([$10],0) as [$10],isnull([$5],0) as [$5],isnull([$1],0) as [$1],isnull([HalfDollar],0) as [HalfDollar],isnull(Quarter,0) as Quarter,isnull(Dime,0) as Dime,isnull(Nickel,0) as Nickel,isnull(Penny,0) as Penny
from 
(Select a.MyValue,MyName,Howmany
from @Test a
group by a.MyValue,MyName,HowMany) p
Pivot 
(sum(HowMany) 
for MyName in ([$100],[$50],[$20],[$10],[$5],[$1],[HalfDollar],Quarter,Dime,Nickel,Penny)
) a
Inner Join
(Select max(passed) as Passed ,Myvalue
from 
@Test
group by myvalue
) b
on a.Myvalue = b.Myvalue

If you notice on the 4545.3340 amount it fails because no US money amount can be smaller than .01

Please feel free to tweak however.

Success is 10% Intelligence, 70% Determination, and 22% Stupidity.
\_/ _/ _/\_/ _/\_/ _/ _/- 881

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2009-12-17 : 16:11:40

also, here is how you can test by omiting certain coinage. Obviously I am using the US Dollar system, since I am not familiar with the UK currency, but you should be able to easily switch.


Declare @Test table(MyOrder int  identity(1,1) Primary Key Clustered , Myvalue decimal(12,4),MyName varchar(20),Cents decimal(10,4),HowMany Decimal(12,4),Passed int, test money)
Insert Into @TEst(MyValue,MyName,Cents)
Select b.MyValue,a.* from
(
--select 'Penny'as n,.01 as amount Union all
--select 'Nickel',.05 Union all
select 'Dime' as n,.10  as amount Union all
--select 'Quarter',.25 Union all
select 'Half Dollar',.50 Union all
select '$1',1.0 Union all
select '$5',5.0 Union all
select '$10',10.0 Union all
select '$20',20.0 Union all
select '$50',50.0 Union all
select '$100',100.0 
) a
Cross Join
(
Select .02 as MyValue Union All 
Select .30 Union All 
Select 4545.32 Union All 
Select 45325.33 as myvalue
) b
order by b.MyValue,a.amount desc

Success is 10% Intelligence, 70% Determination, and 22% Stupidity.
\_/ _/ _/\_/ _/\_/ _/ _/- 881

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-12-18 : 05:03:33

quote:
Originally posted by Arnold Fribble

Shame it produces the wrong answer, e.g.

SELECT 1 AS [RowNo]
, 10 AS [1p]
, 0 AS [2p]
, 0 AS [5p]
, 0 AS [10p]
, 3 AS [20p]
, 2 AS [50p]
, 0 AS [1UKP]
, 110 AS Target
INTO #problem

Hmm, Yup, it's pretty busted! Can't think of a way to get round this issue without lots more loops.

I think I'll try some of the large cross join methods.

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2009-12-19 : 17:30:36

quote:
Originally posted by Transact Charlie

quote:
Originally posted by Arnold Fribble

Shame it produces the wrong answer, e.g.

SELECT 1 AS [RowNo]
, 10 AS [1p]
, 0 AS [2p]
, 0 AS [5p]
, 0 AS [10p]
, 3 AS [20p]
, 2 AS [50p]
, 0 AS [1UKP]
, 110 AS Target
INTO #problem

Hmm, Yup, it's pretty busted! Can't think of a way to get round this issue without lots more loops.

I think I'll try some of the large cross join methods.

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

I did NOT try this with your sample data size... lol




CREATE CLUSTERED INDEX ci_rowNo ON #problem (rowNo)

--create a numbers table

	IF OBJECT_ID('tempDb..#numbers') IS NOT NULL DROP TABLE #numbers

	select n.number 
	into #numbers
	from DBO.F_TABLE_NUMBER_RANGE(0,10000) n

--build the products of the coin amounts

	IF OBJECT_ID('tempDb..#product') IS NOT NULL DROP TABLE #product

	select 
		m.rowNo, m.target, 
		a.coinCt n100,
		b.coinCt n50,
		c.coinCt n20,
		d.coinCt n10,
		e.coinCt n5,
		f.coinCt n2,
		g.coinCt n1,
		a.coinAmt + b.coinAmt + c.coinAmt + d.coinAmt + e.coinAmt + f.coinAmt + g.coinAmt as ttlAmt,
		a.coinCt + b.coinCt + c.coinCt + d.coinCt + e.coinCt + f.coinCt + g.coinCt as ttlCoins
	into #product
	from #problem m,
			(
				select rowNo, n.number as coinCt, n.number * 100 as coinAmt
				from #problem m, #numbers n
				where n.number <= [1UKP] 
			) a,

			(
				select rowNo, n.number as coinCt, n.number * 50 as coinAmt
				from #problem m, #numbers n
				where n.number <= [50p] 
			) b,
			(
				select rowNo, n.number as coinCt, n.number * 20 as coinAmt
				from #problem m, #numbers n 
				where n.number <= [20p]
			) c,
			(
				select rowNo, n.number as coinCt, n.number * 10 as coinAmt
				from #problem m, #numbers n 
				where n.number <= [10p]
			) d,
			(
				select rowNo, n.number as coinCt, n.number * 5 as coinAmt
				from #problem m, #numbers n 
				where n.number <= [5p] 
			) e,
			(
				select rowNo, n.number as coinCt, n.number * 2 as coinAmt
				from #problem m, #numbers n
				where n.number <= [2p] 
			) f,
			(
				select rowNo, n.number as coinCt, n.number * 1 as coinAmt
				from #problem m, #numbers n
				where n.number <= [1p] 
			) g

	where m.rowNo = a.rowNo 
			and m.rowNo = b.rowNo 
				and m.rowNo = c.RowNo 
					and m.rowNo = d.RowNo 
						and m.rowNo = e.rowNo 
							and m.rowNo = f.rowNo 
								and m.rowNo = g.rowNo
			and a.coinAmt + b.coinAmt + c.coinAmt + d.coinAmt + e.coinAmt + f.coinAmt + g.coinAmt = m.target

--result

	select distinct p.*, mi.minCoinCt, n1, n2, n5, n10, n20, n50, n100
	from #problem p
	join #product m on p.rowNo = m.rowNo
	join 
	(
		select 
			rowNo,
			min(ttlCoins) minCoinCt
		from
		(
			select * 
			from #product
		) c
		group by rowNo
	) mi on m.rowNo = mi.rowNo and mi.minCoinCt = m.ttlCoins

EDIT: ~took about 3 minutes to do 10K on my laptop

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 02:47:24

Using Arnold's sample data with my algorithm (which khtan posted a link for), it takes 3 milliseconds and returns

1 piece of 50
3 piece of 20

And for the original problem of 1.93, I get 6 coins (not 7) within 3 milliseconds.

1 piece  of 100
1 piece  of  50
2 pieces of  20
1 piece  of   2
1 piece  of   1

N 56°04'39.26"
E 12°55'05.63"

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2009-12-20 : 09:38:57

quote:
Originally posted by Peso

Using Arnold's sample data with my algorithm (which khtan posted a link for), it takes 3 milliseconds and returns
1 piece of 50
3 piece of 20

And for the original problem of 1.93, I get 6 coins (not 7) within 3 milliseconds.
1 piece of 100
1 piece of 50
2 pieces of 20
1 piece of 2
1 piece of 1

N 56°04'39.26"
E 12°55'05.63"

Looks good Peso... Speedy - and resolves the <n items> issue with a brute force cross join approach...

I see you have checked out Hugo's stuff

http://sqlblog.com/blogs/hugo_kornelis/archive/tags/Bin%20Packing/default.aspx

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 10:50:22

Not really. I started developing this algorithm before his blog posts.
You can see on this forum how it has evolved. The first few versions is ugly and not fast.

N 56°04'39.26"
E 12°55'05.63"

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 11:24:36

Here is an algorithm that takes care of the original problem (100,000 records) in 2 seconds.
First, the function

CREATE FUNCTION dbo.fnGetBinItems
(
	@Items INT,
	@Amount INT,
	@Target INT
)
RETURNS INT
AS
BEGIN
	RETURN	CASE
			WHEN @Items <= @Target / @Amount THEN @Items
			ELSE @Target / @Amount
		END
END

And then the query

SELECT	dbo.fnGetBinItems([1p], 1, [Target] - [1UKP] * 100 - [50p] * 50 - [20p] * 20 - [5p] * 5 - [2p] * 2) AS [1p],
	[2p],
	[5p],
	[20p],
	[50p],
	[1UKP],
	[Target]
FROM	(
		SELECT	[1p],
			dbo.fnGetBinItems([2p], 2, [Target] - [1UKP] * 100 - [50p] * 50 - [20p] * 20 - [5p] * 5) AS [2p],
			[5p],
			[20p],
			[50p],
			[1UKP],
			[Target]
		FROM	(
				SELECT	[1p],
					[2p],
					dbo.fnGetBinItems([5p], 5, [Target] - [1UKP] * 100 - [50p] * 50 - [20p] * 20) AS [5p],
					[20p],
					[50p],
					[1UKP],
					[Target]
				FROM	(
						SELECT	[1p],
							[2p],
							[5p],
							dbo.fnGetBinItems([20p], 20, [Target] - [1UKP] * 100 - [50p] * 50) AS [20p],
							[50p],
							[1UKP],
							[Target]
						FROM	(
								SELECT	[1p],
									[2p],
									[5p],
									[20p],
									dbo.fnGetBinItems([50p], 50, [Target] - [1UKP] * 100) AS [50p],
									[1UKP],
									[Target]
								FROM	(
										SELECT	[1p],
											[2p],
											[5p], 
											[20p],
											[50p],
											dbo.fnGetBinItems([1UKP], 100, [Target]) AS [1UKP],
											[Target]
										FROM	#Problem
									) AS d
							) AS d
						) AS d
				) AS d
		) AS d

N 56°04'39.26"
E 12°55'05.63"

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2009-12-20 : 11:56:09

quote:
Originally posted by Peso

Here is an algorithm that takes care of the original problem (100,000 records) in 2 seconds...

Very elegant...

Unfortunately, this (Sort/First-Fit) approach fails the "Fribble" test producing 12 coins instead of the desired 4.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 16:09:26

Ok, wait a minute. Or two...

N 56°04'39.26"
E 12°55'05.63"

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 16:40:30

[code]SELECT p.RowNo,
p.[1p],
p.[2p],
p.[5p],
p.[10p],
p.[20p],
p.[50p],
p.[1UKP],
p.[Target],
z.[1p],
z.[2p],
z.[5p],
z.[10p],
z.[20p],
z.[50p],
z.[1UKP]
FROM Problem AS p
CROSS APPLY (
SELECT TOP(1) a.Number AS [1p],
b.Number AS [2p],
c.Number AS [5p],
d.Number AS [10p],
e.Number AS [20p],
f.Number AS [50p],
g.Number AS [1UKP]
FROM master..spt_values AS a
INNER JOIN master..spt_values AS b ON b.Type = 'P'
AND b.Number <= p.[2p]
AND b.Number <= p.[Target] / 2
INNER JOIN master..spt_values AS c ON c.Type = 'P'
AND c.Number <= p.[5p]
AND c.Number <= p.[Target] / 5
INNER JOIN master..spt_values AS d ON d.Type = 'P'
AND d.Number <= p.[10p]
AND d.Number <= p.[Target] / 10
INNER JOIN master..spt_values AS e ON e.Type = 'P'
AND e.Number <= p.[20p]
AND e.Number <= p.[Target] / 20
INNER JOIN master..spt_values AS f ON f.Type = 'P'
AND f.Number <= p.[50p]
AND f.Number <= p.[Target] / 50
INNER JOIN master..spt_values AS g ON g.Type = 'P'
AND g.Number <= p.[1UKP]
AND g.Number <= p.[Target] / 100
WHERE a.Type = 'P'
AND a.Number <= p.[1p]
AND a.Number <= p.[Target]
AND a.Number + b.Number * 2 + c.Number * 5 + d.Number * 10 + e.Number * 20 + f.Number * 50 + g.Number * 100 = p.[Target]
ORDER BY a.Number + b.Number + c.Number + d.Number + e.Number + f.Number + g.Number
) AS z
WHERE p.[1p] + p.[2p] * 2 + p.[5p] * 5 + p.[10p] * 10 + p.[20p] * 20 + p.[50p] * 50 + p.[1UKP] * 100 >= p.[Target]
AND p.[Target] > 0[/code]

N 56°04'39.26"
E 12°55'05.63"

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2009-12-20 : 17:25:46

quote:
Originally posted by Peso

...CROSS APPLY...

N 56°04'39.26"
E 12°55'05.63"

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 17:35:43

Or this, which runs in less than 40 seconds for the full 100,001 sample data...


CREATE CLUSTERED INDEX CX_Problem ON #Problem ([Target])

CREATE TABLE	#Tally
		(
			Amount AS ([1p] + [2p] * 2 + [5p] * 5 + [10p] * 10 + [20p] * 20 + [50p] * 50 + [1UKP] * 100) PERSISTED,
			Items AS ([1p] + [2p] + [5p] + [10p] + [20p] + [50p] + [1UKP]) PERSISTED,
			[1p] INT NOT NULL,
			[2p] INT NOT NULL,
			[5p] INT NOT NULL,
			[10p] INT NOT NULL,
			[20p] INT NOT NULL,
			[50p] INT NOT NULL,
			[1UKP] INT NOT NULL
		)

CREATE UNIQUE CLUSTERED INDEX IX_Tally ON #Tally (Amount, Items, [1p], [2p], [5p], [10p], [20p], [50p], [1UKP])

INSERT		#Tally
		(
			[1p],
			[2p],
			[5p],
			[10p],
			[20p],
			[50p],
			[1UKP]
		)
SELECT		a.Number AS [1p],
		b.Number AS [2p],
		c.Number AS [5p],
		d.Number AS [10p],
		e.Number AS [20p],
		f.Number AS [50p],
		g.Number AS [1UKP]
FROM		(
			SELECT	MIN([1p]) AS [1p],
				MIN([2p]) AS [2p],
				MIN([5p]) AS [5p],
				MIN([10p]) AS [10p],
				MIN([20p]) AS [20p],
				MIN([50p]) AS [50p],
				MIN([1UKP]) AS [1UKP]
			FROM	(
					SELECT	MAX([1p]) AS [1p],
						MAX([2p]) AS [2p],
						MAX([5p]) AS [5p],
						MAX([10p]) AS [10p],
						MAX([20p]) AS [20p],
						MAX([50p]) AS [50p],
						MAX([1UKP]) AS [1UKP]
					FROM	#Problem

					UNION ALL

					SELECT	MAX(Target / NULLIF([1p], 0)) AS [1p],
						MAX(Target / 2 / NULLIF([2p], 0)) AS [2p],
						MAX(Target / 5 / NULLIF([5p], 0)) AS [5p],
						MAX(Target / 10 / NULLIF([10p], 0)) AS [10p],
						MAX(Target / 20 / NULLIF([20p], 0)) AS [20p],
						MAX(Target / 50 / NULLIF([50p], 0)) AS [50p],
						MAX(Target / 100 / NULLIF([1UKP], 0)) AS [1UKP]
					FROM	#Problem
				) AS d
		) AS z
INNER JOIN	master..spt_values AS a ON a.Type = 'P'
			AND a.Number <= z.[1p]
INNER JOIN	master..spt_values AS b ON b.Type = 'P'
			AND b.Number <= z.[2p]
INNER JOIN	master..spt_values AS c ON c.Type = 'P'
			AND c.Number <= z.[5p]
INNER JOIN	master..spt_values AS d ON d.Type = 'P'
			AND d.Number <= z.[10p]
INNER JOIN	master..spt_values AS e ON e.Type = 'P'
			AND e.Number <= z.[20p]
INNER JOIN	master..spt_values AS f ON f.Type = 'P'
			AND f.Number <= z.[50p]
INNER JOIN	master..spt_values AS g ON g.Type = 'P'
			AND g.Number <= z.[1UKP]
WHERE		a.Number + b.Number + c.Number + d.Number + e.Number + f.Number + g.Number > 0
ORDER BY	[1p] + [2p] * 2 + [5p] * 5 + [10p] * 10 + [20p] * 20 + [50p] * 50 + [1UKP] * 100,
		[1p] + [2p] + [5p] + [10p] + [20p] + [50p] + [1UKP]

;WITH cteYak
AS (
	SELECT		p.RowNo,
			p.[1p],
			p.[2p],
			p.[5p],
			p.[10p],
			p.[20p],
			p.[50p],
			p.[1UKP],
			p.[Target],
			t.[1p] AS [1t],
			t.[2p] AS [2t],
			t.[5p] AS [5t],
			t.[10p] AS [10t],
			t.[20p] AS [20t],
			t.[50p] AS [50t],
			t.[1UKP] AS [100t],
			ROW_NUMBER() OVER (PARTITION BY p.RowNo ORDER BY t.Items) AS recID
	FROM		(
				SELECT	RowNo,
					[1p],
					[2p],
					[5p],
					[10p],
					[20p],
					[50p],
					[1UKP],
					[Target]
				FROM	#Problem
				WHERE	[1p] + [2p] + [5p] + [10p] + [20p] + [50p] + [1UKP] > 0
					AND [Target] > 0
			) AS p
	INNER HASH JOIN	#Tally AS t ON t.Amount = p.[Target]
	WHERE		t.[1p] <= p.[1p]
			AND t.[2p] <= p.[2p]
			AND t.[5p] <= p.[5p]
			AND t.[10p] <= p.[10p]
			AND t.[20p] <= p.[20p]
			AND t.[50p] <= p.[50p]
			AND t.[1UKP] <= p.[1UKP]
)
SELECT	RowNo,
	[1p],
	[2p],
	[5p],
	[10p],
	[20p],
	[50p],
	[1UKP],
	[Target],
	[1t] AS [1p],
	[2t] AS [2p],
	[5t] AS [5p],
	[10t] AS [10p],
	[20t] AS [20p],
	[50t] AS [50p],
	[100t] AS [1UKP]
FROM	cteYak
WHERE	recID = 1

DROP TABLE	#Tally

N 56°04'39.26"
E 12°55'05.63"

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2009-12-20 : 17:46:20

quote:
Originally posted by Peso

Or this, which runs in less than a minute...
...WITH cteYak...

Very nice. 25 seconds for the full set (on my box).

Time for me to clean out the cobwebs and bust out the 2005 BOL. Thanks for the contributions!

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-20 : 18:00:19

Try the new version. There is now a clustered index on #Problem and an added join hint in the cte.

N 56°04'39.26"
E 12°55'05.63"

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-12-21 : 04:54:39

Pretty sweet peso.

~~Does an INNER HASH JOIN perform an inner join but force the optimiser to use a hash join rather than any other method?~~

Never mind -- I should just read the documentation!

sorry.

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-12-21 : 05:02:55

Yes. Since there are two clustered indexes, the optimizer could go for a MERGE inner join join instead because the data is sort of sorted

So I added the HASH hint to make sure hashes are used due to the amount of data.

What time do you get on your computer?

N 56°04'39.26"
E 12°55'05.63"

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources