求一存储过程或函数（几个记录之和等于某一固定值）,关键是速度

Question

--示例表：
create table music(id int identity(1,1),length int)
insert music select 200
union all select 249
union all select 58
union all select 109
union all select 344
union all select 294
union all select 43
union all select 296
union all select 87
union all select 102
union all select 336
union all select 158
union all select 265
union all select 332
union all select 132
union all select 252
union all select 275
union all select 243
union all select 228
union all select 205
union all select 324
union all select 164
union all select 30
union all select 268
union all select 105
union all select 84
union all select 34
union all select 285
union all select 73
union all select 159
union all select 154
union all select 77
union all select 261
union all select 71
union all select 101
union all select 94
union all select 133
union all select 251
union all select 80
union all select 296
union all select 314
union all select 338
union all select 25
union all select 330
union all select 218
union all select 198
union all select 300
union all select 307
union all select 123
union all select 342
union all select 33
union all select 106
union all select 261
union all select 137
union all select 281
union all select 309
union all select 278
union all select 336
union all select 319
union all select 212
union all select 353
union all select 323
union all select 8
union all select 42
union all select 226
union all select 168
union all select 61
union all select 325
union all select 318
union all select 155
union all select 103
union all select 77
union all select 39
union all select 297
union all select 181
union all select 196
union all select 256
union all select 196
union all select 166
union all select 182
union all select 165
union all select 151
union all select 244
union all select 79
union all select 252
union all select 315
union all select 286
union all select 205
union all select 331
union all select 220
union all select 249
union all select 248
union all select 342
union all select 42
union all select 82
union all select 244
union all select 224
union all select 193
union all select 166
union all select 141
union all select 230
union all select 296
union all select 123
union all select 177
union all select 100
union all select 114
union all select 216
union all select 229
union all select 220
union all select 108
union all select 179
union all select 229
union all select 134
union all select 274
union all select 164
union all select 335
union all select 59
union all select 206
union all select 274
union all select 287
union all select 181
union all select 257
union all select 318
union all select 341
union all select 59
union all select 360
union all select 309
union all select 158
union all select 52
union all select 264
union all select 83
union all select 352
union all select 311
union all select 46
union all select 84
union all select 271
union all select 252
union all select 102
union all select 337
union all select 285
union all select 342
union all select 238
union all select 273
union all select 206
union all select 92
union all select 272
union all select 169
union all select 333
union all select 89
union all select 22
union all select 98
union all select 35
union all select 38
union all select 9
union all select 350
union all select 128
union all select 303
union all select 150
union all select 339
union all select 342
union all select 109
union all select 34
union all select 125
union all select 22
union all select 176
union all select 172
union all select 96
union all select 259
union all select 35

Answer 1

注意表music有近两万条记录！！

Answer 2

create clustered index i_music_length on music(length)
表music有length上的聚集索引

Answer 3

"如果没有这种组合，就列出n个length之和最接近3600的一个组合。"
穷举, 没有速度可言.

Answer 4

谢谢hinco,能写个例子吗？谢谢

Answer 5

to:fcuandy(手中无剑,心中亦无) 
如果没有这种组合,不列出也可以，只列出有的即可。
多谢！！

Answer 6

to:libin_ftsafe(子陌红尘：当libin告别ftsafe)
能写个速度较快的例子吗？
多谢

Answer 7

hinco(桃色德鲁依) ( ) 信誉：100    Blog  2006-12-19 17:56:25  得分: 0  
 
 
   
这个是算法问题……要速度的话，建议还是不要找最优解了，“贪心”一点，随机取id，累加到接近一小时就好了，速度才有保证----------------------------------------------------------
问题是，他限定的个数N 
 

Answer 8

抛砖引玉--生成随机数据使用了邹老大的代码-- 定义开始和结束范围
DECLARE @beginid int, @endid int
SELECT 
@beginid = 5,
@endid = 360-- 生成随机数据SELECT TOP 20000 
id=IDENTITY(int,1,1),
length = (ABS(CHECKSUM(NEWID())) %  (@endid - @beginid + 1)) + @beginid
INTO tb
FROM sysobjects a,sysobjects b,sysobjects cgo
--存储过程
Create proc p_test
@N int
as--随机产生数据
declare @t table(id int IDENTITY(1,1),tid int,length int)
set rowcount @N
insert @t(tid,length)
select id,length from tb order by newid()set rowcount 0--先调整到<=3600
declare @tid int
declare @id intwhile (select sum(length) from @t)>3600
begin
  select top 1 @tid=tid from @t order by length desc
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=(select top 1 id from tb 
    where length<t.length 
    and id not in (select tid from @t)
    order by newid()
    )
end--开始调大
while (select sum(length) from @t)<3600 and exists (
   select 1 from @t t,tb b
   where t.tid<>b.id
   and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
)
begin
  select top 1 @tid=t.tid,@id=b.id
  from @t t,tb b
  where t.tid<>b.id
  and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
  order by 3600-(select sum(length) from @t)-(b.length-t.length)  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=@id
end--显示数据
select * from @tselect sum(length) as sLength from @tgo
--调用
exec p_test 20

Answer 9

存储过程有错，修改如下--存储过程
alter proc p_test
@N int
as--随机产生数据
declare @t table(id int IDENTITY(1,1),tid int,length int)
set rowcount @N
insert @t(tid,length)
select id,length from tb order by newid()set rowcount 0--先调整到<=3600
declare @tid int
declare @id intwhile (select sum(length) from @t)>3600
begin
  select top 1 @tid=tid from @t order by length desc
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=(select top 1 id from tb 
    where length<t.length 
    and id not in (select tid from @t)
    order by newid()
    )
end--开始调大
while (select sum(length) from @t)<3600 and exists (
   select 1 from @t t,tb b
   where t.tid<>b.id
   and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.id not in (select tid from @t)
)
begin
  select top 1 @tid=t.tid,@id=b.id
  from @t t,tb b
  where t.tid<>b.id
  and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
  and b.id not in (select tid from @t)
  order by 3600-(select sum(length) from @t)-(b.length-t.length)  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=@id
end--显示数据
select * from @tselect sum(length) as sLength from @tgo

Answer 10

速度和参数@N的值有关@N>100的时候很慢，我这里要几分钟，现在测试的结果都是能找到正好3600的组合

Answer 11

晕，没人参与，搞得我要换号
贴个运行结果（我的破电脑用时3分49秒）--调用
exec p_test 120
go
--结果
id          tid         length      
----------- ----------- ----------- 
1           329         15
2           14800       42
3           5039        28
4           11179       32
5           1621        49
6           4204        9
7           12793       10
8           6304        48
9           4292        16
10          3572        29
11          18805       30
12          9251        20
13          4937        5
14          5536        35
15          18171       16
16          9668        39
17          15467       9
18          7838        17
19          16049       19
20          19330       23
21          14697       30
22          6714        39
23          18786       27
24          12052       47
25          16922       42
26          5740        38
27          6962        18
28          12816       25
29          18983       6
30          5856        21
31          17324       51
32          9864        40
33          8024        32
34          7051        42
35          13226       8
36          17147       9
37          3483        36
38          5210        25
39          7843        26
40          10411       52
41          19844       46
42          17172       29
43          19447       8
44          14357       51
45          1730        17
46          4420        25
47          16655       31
48          14869       54
49          8476        9
50          1675        42
51          18817       45
52          6929        45
53          15266       55
54          3117        28
55          3545        51
56          17955       50
57          4688        18
58          796         54
59          12802       52
60          15721       32
61          2945        48
62          4063        26
63          11223       23
64          1452        18
65          14162       30
66          13035       38
67          1663        43
68          8202        18
69          15757       23
70          14314       16
71          7181        30
72          10930       46
73          15378       37
74          3021        53
75          16651       53
76          4360        20
77          19383       46
78          15318       37
79          5191        23
80          2796        29
81          12015       54
82          2570        18
83          15681       37
84          2714        38
85          12667       26
86          7498        15
87          19881       54
88          16191       11
89          11124       20
90          19672       15
91          17662       10
92          8737        41
93          7094        33
94          14647       6
95          5067        6
96          5142        13
97          7070        6
98          18621       16
99          13044       9
100         10769       39
101         2364        31
102         401         32
103         2588        51
104         17051       17
105         15797       49
106         2337        39
107         7992        18
108         14961       13
109         4972        8
110         16969       50
111         11314       43
112         14258       23
113         3181        40
114         13381       34
115         8319        10
116         10846       30
117         18992       51
118         1550        12
119         3076        51
120         16876       27（所影响的行数为 120 行）sLength     
----------- 
3600（所影响的行数为 1 行）

Answer 12

多谢libin_ftsate(冒牌子陌红尘：当libin告别ftsate V0.1) 
除了速度不是很理想外，另外还有时候找不到这种组合，即正好=3600的N个组合不存在，
实际上是存在的。
这个不知该如何处理？？
谢谢！！

Answer 13

--存储过程
ALTER  proc p_test
@N int
as--随机产生数据
declare @t table(id int IDENTITY(1,1),tid int,length int)
set rowcount @N
insert @t(tid,length)
select id,length from tb order by newid()set rowcount 0--先调整到<=3600
declare @tid int
declare @id intwhile (select sum(length) from @t)>3600
begin
  select top 1 @tid=tid from @t order by length desc
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=(select top 1 id from tb 
    where length<t.length 
    and id not in (select tid from @t)
    order by newid()
    )
end--开始调大
while (select sum(length) from @t)<3600 and exists (
   select 1 from @t t,tb b
   where t.tid<>b.id
   and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.length>t.length
   and b.id not in (select tid from @t)
)
begin
  select top 1 @tid=t.tid,@id=b.id
  from @t t,tb b
  where t.tid<>b.id
  and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.length>t.length
  and b.id not in (select tid from @t)
  order by 3600-(select sum(length) from @t)-(b.length-t.length)  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=@id
end--显示数据
select * from @tselect sum(length) as sLength from @t
GO

Answer 14

to :pao1uo(一天到晚冒牌的鱼 V0.1)
谢谢！！
这样还会找不到N个组合起来，其和=3600
实际上存在。麻烦再看看

Answer 15

to:fcuandy(手中无剑,心中亦无) 
能求相近可大于小于或等于,不能求最按近, 否则只能穷举
---------------------------------------------------------------也可以，关键是得有个差不多的结果。速度当然也很重要。有什么好办法吗？谢了！！

Answer 16

lz的数据给我下说明下用哪个N的时候会出现
找不到N个组合起来，其和=3600
实际上存在。的情况

Answer 17

或者试下用以下改过调整方法的存储过程--存储过程
ALTER  proc p_test
@N int
as--随机产生数据
declare @t table(id int IDENTITY(1,1),tid int,length int)
set rowcount @N
insert @t(tid,length)
select id,length from tb order by newid()set rowcount 0--先调整到<=3600
declare @tid int
declare @id intwhile (select sum(length) from @t)>3600
begin
  select top 1 @tid=tid from @t order by length desc
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=(select top 1 id from tb 
    where length<t.length 
    and id not in (select tid from @t)
    order by newid()
    )
end--开始调大
while (select sum(length) from @t)<3600 and exists (
   select 1 from @t t,tb b
   where t.tid<>b.id
   and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.length>t.length
   and b.id not in (select tid from @t)
)
begin
  select top 1 @tid=t.tid,@id=b.id
  from @t t,tb b
  where t.tid<>b.id
  and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.length>t.length
  and b.id not in (select tid from @t)
  order by case when 3600-(select sum(length) from @t)-(b.length-t.length)=0 then 0 else 1 end,newid()
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=@id
end--显示数据
select * from @tselect sum(length) as sLength from @t
GO

Answer 18

用楼主在1楼给的169条记录的数据测试我的存储过程：N=10  由于最大10条的总和只有3468，每次测试都出这10条，用时<1秒
N=11  总和只有3600，用时<1秒
N=12  总和只有3600，用时<1秒
N=20  总和只有3600，用时<1秒
N=40  总和只有3600，用时<1秒
N=50  总和只有3600，用时<1秒
N=51  总和只有3600，用时<1秒
N=52  由于最小的52条总和3702，死循环

Answer 19

to:j9988(j9988)
帮帮忙，写个存储过程吧
多谢了

Answer 20

多谢pao1uo(一天到晚冒牌的鱼 V0.1)
我再试试看

Answer 21

修正死循环（觉得没什么可改的了）--存储过程
ALTER  proc p_test
@N int
as--随机产生数据
declare @t table(id int IDENTITY(1,1),tid int,length int)
set rowcount @N
insert @t(tid,length)
select id,length from tb order by newid()set rowcount 0--先调整到<=3600
declare @tid int
declare @id intwhile (select sum(length) from @t)>3600 and exists (
select 1 from @t t,tb b
where t.length>b.length
and b.id not in (select tid from @t)
)
begin
  select top 1 @tid=tid from @t order by length desc
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=(select top 1 id from tb 
    where length<t.length 
    and id not in (select tid from @t)
    order by newid()
    )
end--开始调大
while (select sum(length) from @t)<3600 and exists (
   select 1 from @t t,tb b
   where t.tid<>b.id
   and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.length>t.length
   and b.id not in (select tid from @t)
)
begin
  select top 1 @tid=t.tid,@id=b.id
  from @t t,tb b
  where t.tid<>b.id
  and 3600-(select sum(length) from @t)-(b.length-t.length)>=0
   and b.length>t.length
  and b.id not in (select tid from @t)
  order by case when 3600-(select sum(length) from @t)-(b.length-t.length)=0 then 0 else 1 end,newid()
  update t
  set tid=b.id,length=b.length
  from @t t,tb b
  where t.tid=@tid
  and b.id=@id
end--显示数据
select * from @tselect sum(length) as sLength from @t
GO

Answer 22

pao1uo(一天到晚冒牌的鱼 V0.1)的方案很好了.

Answer 23

p_test 80 耗时1分38秒
p_test 100 耗时2分15秒
p_test 120 耗时3分51秒

Answer 24

to:j9988pao1uo(一天到晚冒牌的鱼 V0.1)的方案好像和你提出的方案不太一样啊
究竟哪个效率更高些啊？

Answer 25

老大的贴子中有这类问题的通用解法：
http://blog.csdn.net/zjcxc/archive/2004/08/06/67518.aspx但记录量一大，根本运行不了，时间超长。哪位能改一下呢？
其实我只要得到一个组合就可以了。没必要找出所有组合。谢谢！！

Answer 26

ALTER Proc pGetIds @n int
 
AS BEGIN --DECLARE @n int --歌曲个数
DECLARE @t TABLE  (id int,length int ,uid  int  IDENTITY(1,1),diff int)
DECLARE @AVG int
DECLARE @CurTotal int --当前计算的结果
DECLARE @Times int --循环次数
DECLARE @Result TABLE (length int ,ids varchar(800))
DECLARE @IDS  varchar(800)
 
--初始化
--SET  @n = 10
SET  @AVG = 0
SET @CurTotal = 0 
SET @Times = 0 
SET @IDS = ''SELECT @AVG  = 3600 /@n INSERT INTO @t(id,length) SELECT   TOP 120  ID,LENGTH FROM music order by abs(@AVG - length) 
DELETE FROM @t WHERE uid > @n
SELECT @CurTotal = SUM(LENGTH) FROM @t
SELECT @IDS =  @IDS +CAST(ID AS varchar(6)) +',' FROM @t
INSERT INTO @Result SELECT @CurTotal,@IDS
 WHILE @Times < 10 AND  ABS(@CurTotal - 3600)>0BEGIN--计算替换掉每个长度后与总数的差
UPDATE @t SET diff = BB.diff FROM  @t AS AA INNER JOIN ( 

SELECT  B.UID,3600- (select SUM(length) from @t as AA where AA.uid !=B.uid) as diff   FROM @t AS B
) AS BB ON AA.UID = BB.UId  ----从现在库中找到一个与差值最近的记录替换掉
Update @t SET id = BB.ID,length = BB.length FROM @t AS AA  INNER JOIN (
select TOP 1 A.UID,B.ID,b.length from @t AS A inner join music AS b ON A.ID != B.ID ORDER BY ABS(A.diff-b.length)) AS BB ON   AA.uid = BB.uID  
SELECT @CurTotal = SUM(LENGTH) FROM @t
SELECT  @IDS = ''
SELECT @IDS =  @IDS +CAST(ID AS varchar(6)) +',' FROM @t
INSERT INTO @Result SELECT @CurTotal,@IDS
 
 
SET @Times = @Times +1END SELECT @IDS = AA.ids from (select top 1 ids  FROM @Result order by abs(length-3600)
) AS AASELECT @CurTotal
 
SELECT @IDS
 
--RETURN  @idsEND

Answer 27

to:cpp2017(幕白兄)
测试了一下，你的速度好快。原理正在看。继续测试，看原理。首先表示感谢