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

Our new SQL Server Forums are live! Come on over! We've restricted the ability to create new threads on these forums.

SQL Server Forums
Profile | Active Topics | Members | Search | Forum FAQ
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 General SQL Server Forums
 Script Library
 Selecting rows with sums equal to a given number
 Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

Stoad
Freaky Yak Linguist

*
1983 Posts

Posted - 11/02/2003 :  18:04:20  Show Profile  Visit Stoad's Homepage  Reply with Quote
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.

Edited by - Stoad on 11/03/2003 02:40:42

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 11/03/2003 :  08:46:25  Show Profile  Reply with Quote
Isn't that the subset sum problem?
Go to Top of Page

Stoad
Freaky Yak Linguist

*
1983 Posts

Posted - 11/03/2003 :  08:59:19  Show Profile  Visit Stoad's Homepage  Reply with Quote
Exactly, Arnold. LOL :) And what then??
Go to Top of Page

Arnold Fribble
Yak-finder General

United Kingdom
1961 Posts

Posted - 11/03/2003 :  11:54:29  Show Profile  Reply with Quote
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
Go to Top of Page

Stoad
Freaky Yak Linguist

*
1983 Posts

Posted - 11/03/2003 :  14:51:06  Show Profile  Visit Stoad's Homepage  Reply with Quote
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.
Go to Top of Page
  Previous Topic Topic Next Topic  
 Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.04 seconds. Powered By: Snitz Forums 2000