Selecting rows with sums equal to a given number

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

General SQL Server Forums

Script Library

Selecting rows with sums equal to a given number

Author

Topic

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2003-11-02 : 18:04:20

You are given say a pricelist of books. And you have to find out
all possible sets of books, each of them having total sum of book
prices equal to a given number.

set nocount on
if object_id('tempdb..#t')>0 drop table #t
if object_id('tempdb..#tt')>0 drop table #tt
create table #t (n int, price int)
insert into #t -- note asc order of book prices
select 1, 1 union all
select 2, 3 union all
select 3, 4 union all
select 4, 5 union all
select 5, 7 union all
select 6, 7 union all
select 7, 11 union all
select 8, 15 union all
select 9, 20 union all
select 10, 20 union all
select 11, 22 union all
select 12, 28 union all
select 13, 33 union all
select 14, 40 union all
select 15, 43 union all
select 16, 47 union all
select 17, 50 union all
select 18, 55 union all
select 19, 56 union all
select 20, 63
go
create table #tt (n int, price int)
go
declare @rows int, @p int, @sum int set @sum=16
delete from #t where price>@sum
set @p=(select sum(price) from #t)

if @p>=@sum
begin
set @rows=(select max(n) from #t)
declare @n int, @s int
set @n=@rows+1 set @s=0

while 0=0
begin
while @n>1
begin
set @n=@n-1
if @s+(select price from #t where n=@n)<=@sum
and @s+(select sum(price) from #t where n<=@n)>=@sum
begin
set @s=@s+(select price from #t where n=@n)
insert into #tt select n, price from #t where n=@n
if @s=@sum select * from #tt --- outputting
end
end
set @n=(select min(n) from #tt)
set @s=@s-(select price from #tt where n=@n)
delete from #tt where n=@n
if @s=0 and (select sum(price) from #t where n<@n)<@sum break
end

end
drop table #tt
drop table #t

Result for @sum=16 (for e.g. @sum=76 number of different sets = 196):


n           price       
----------- ----------- 
8           15
1           1

n           price       
----------- ----------- 
7           11
4           5

n           price       
----------- ----------- 
7           11
3           4
1           1

n           price       
----------- ----------- 
6           7
4           5
3           4

n           price       
----------- ----------- 
6           7
4           5
2           3
1           1

n           price       
----------- ----------- 
5           7
4           5
3           4

n           price       
----------- ----------- 
5           7
4           5
2           3
1           1

EDIT: added one more condition (in blue) into an IF statement.
Now it works incredibly fast.

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2003-11-03 : 08:46:25

Isn't that the subset sum problem?

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2003-11-03 : 08:59:19

Exactly, Arnold. LOL :) And what then??

Arnold Fribble
Yak-finder General

1961 Posts

Posted - 2003-11-03 : 11:54:29

quote:
And what then??

Don't know, really. I was just pointing out that it's a well-known (and named) problem. And in the general case, it's NP-complete.
Apparently, there's a dynamic-programming solution that's tractable if the problem size is small enough, and other solutions for 'low-density' situations, and other special cases, but I didn't really understand any of it

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2003-11-03 : 14:51:06

quote:
I didn't really understand any of it

LOL, exactly my case!! Plus, I have never even tried to understand them
(as I can remember I was able to understand only the bubble sorting
algorithm, but today I am not sure how exactly it works).

As to my solution, of course it is a simple backtracking. BTW, if we need
to find only one (any) required subset then the code produces it in a few
seconds. Today I tested it against 200 rows with random numbers from 1
to about 900. Got the first subset in 1-5 seconds (depends on the sought
sum)... It is terribly hard to think up such test data that could increase
significantly the time of first finding.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources