| 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 |
|
|
|
Selecting rows with sums equal to a given number