Author |
Topic  |
|
Stoad
Freaky Yak Linguist
*
1983 Posts |
Posted - 11/02/2003 : 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. |
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
|
Isn't that the subset sum problem?
|
 |
|
Stoad
Freaky Yak Linguist
*
1983 Posts |
Posted - 11/03/2003 : 08:59:19
|
Exactly, Arnold. LOL :) And what then?? |
 |
|
Arnold Fribble
Yak-finder General
United Kingdom
1961 Posts |
Posted - 11/03/2003 : 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 - 11/03/2003 : 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. |
 |
|
|
Topic  |
|
|
|