这个问题谁有最简便的解法？300分！

Question

在有限多的不大于100的正整数中，找出尽量多个相加起来值介于98～102之间的组合。
组合的个数限制在2 和3。
 比如有数字（39，40，1，55，17，17……N）数字可以有重复。
找出的组合有（50，50），（21，41，39），（48，50）……M。在上面的数字在组合中每次只能出现一次（比如数字中40只出现过一次，那在组合中也只能出现一次。17出现过两次那在组合中最多两次）要求用最简捷的方法，最少的循环。
分只给提供最优解的人。如果得不到最优解就平分吧？300分保证不食言！

Answer 1

-- 测试数据, value 列放你要处理的数
DECLARE @t TABLE(
id int identity, 
value int)
INSERT @t SELECT 39
UNION ALL SELECT 40
UNION ALL SELECT 5
UNION ALL SELECT 55
UNION ALL SELECT 17
UNION ALL SELECT 17
UNION ALL SELECT 50
UNION ALL SELECT 48
UNION ALL SELECT 82
UNION ALL SELECT 83
-- 组合处理
DECLARE @r TABLE(
id int identity, 
ids varchar(100), 
vs varchar(100))SELECT 
id1 = A.id, value1 = A.value,
id2 = B.id, value2 = B.value,
value = A.value + B.value,
flag = CASE WHEN A.value + B.value BETWEEN 98 AND 102 THEN 1 ELSE 0 END
INTO #1
FROM @t A, @t B
WHERE A.id < B.id-- 二次组合的
INSERT @r
SELECT 
RTRIM(A.id1) + ',' + RTRIM(A.id2), RTRIM(A.value1) + ',' + RTRIM(A.value2)
FROM #1 A
WHERE flag = 1-- 三次组合的
INSERT @r
SELECT 
RTRIM(A.id1) + ',' + RTRIM(A.id2) + ',' + RTRIM(B.ID),
RTRIM(A.value1) + ',' + RTRIM(A.value2) + ',' + RTRIM(B.value)
--SELECT A.value1, A.value2, B.value
FROM #1 A, @t B
WHERE A.id2 < B.id
AND A.flag = 0
AND A.value + B.value BETWEEN 98 AND 102
AND NOT EXISTS(
SELECT * FROM #1 
WHERE flag = 1 
AND B.id in(A.id1, A.id2))-- 删除有重复引用的
SET ROWCOUNT 1
DELETE A FROM @r A
WHERE EXISTS(
SELECT *
FROM @r AA, @t BB
WHERE AA.id < A.id
AND CHARINDEX(',' + RTRIM(BB.id) + ',', ',' + AA.ids + ',') >0
AND CHARINDEX(',' + RTRIM(BB.id) + ',', ',' + A.ids + ',') >0)
WHILE @@ROWCOUNT > 0
DELETE A FROM @r A
WHERE EXISTS(
SELECT *
FROM @r AA, @t BB
WHERE AA.id < A.id
AND CHARINDEX(',' + RTRIM(BB.id) + ',', ',' + AA.ids + ',') >0
AND CHARINDEX(',' + RTRIM(BB.id) + ',', ',' + A.ids + ',') >0)
SET ROWCOUNT 0
SELECT vs FROM @r
GODROP TABLE #1

Answer 2

-- 改用游标, 100条数据在我的电脑中3秒可以出来了.-- 测试数据, value 列放你要处理的数
DECLARE @t TABLE(
id int identity, 
value int)
INSERT @t SELECT TOP 100 ABS(CHECKSUM(NEWID())) % 100 FROM syscolumns-- 组合处理
DECLARE @r TABLE(
id int identity, 
ids varchar(100), 
vs varchar(100))
DECLARE @tid TABLE(id varchar(10))SELECT 
id1 = A.id, value1 = A.value,
id2 = B.id, value2 = B.value,
value = A.value + B.value,
flag = CASE WHEN A.value + B.value BETWEEN 98 AND 102 THEN 1 ELSE 0 END
INTO #1
FROM @t A, @t B
WHERE A.id < B.idDECLARE tb CURSOR STATIC LOCAL
FOR
SELECT ids = ',' + ids + ',', vs
FROM(
-- 二次组合的
SELECT 
ids  = RTRIM(A.id1) + ',' + RTRIM(A.id2), 
vs = RTRIM(A.value1) + ',' + RTRIM(A.value2)
FROM #1 A
WHERE flag = 1
UNION ALL
-- 三次组合的
SELECT 
RTRIM(A.id1) + ',' + RTRIM(A.id2) + ',' + RTRIM(B.ID),
RTRIM(A.value1) + ',' + RTRIM(A.value2) + ',' + RTRIM(B.value)
--SELECT A.value1, A.value2, B.value
FROM #1 A, @t B
WHERE A.id2 < B.id
AND A.flag = 0
AND A.value + B.value BETWEEN 98 AND 102
AND NOT EXISTS(
SELECT * FROM #1 
WHERE flag = 1 
AND B.id in(A.id1, A.id2))
)ADECLARE @ids varchar(100), @values varchar(100)
OPEN tb
FETCH tb INTO @ids, @values
WHILE @@ROWCOUNT > 0
BEGIN
IF NOT EXISTS(
SELECT * FROM @tid WHERE CHARINDEX(id, @ids) > 0)
BEGIN
INSERT @r VALUES(@ids, @values)
INSERT @tid SELECT ',' + RTRIM(id) + ',' FROM @t
WHERE CHARINDEX(',' + RTRIM(id) + ',', @ids) > 0
END
FETCH tb INTO @ids, @values
END
CLOSE tb
DEALLOCATE tbSELECT vs FROM @r
GODROP TABLE #1

Answer 3

老大实在太牛了，能做到这样已经很厉害了！
如果以组合的个数最多为标准，CSDMN有更好的解决方法吗？

Answer 4

--没想出好的算法，但100以内可以利用计算机的能力
--提供一种扫描的方法做参考
declare @Aresult table(id int,a int,b int,c int)
declare @j int
set @j=1
while @j<=5
begin
DECLARE @t TABLE(id int identity(1,1),value int)
--INSERT @t SELECT 39
--UNION ALL SELECT 40
--UNION ALL SELECT 5
--UNION ALL SELECT 55
--UNION ALL SELECT 17
--UNION ALL SELECT 17
--UNION ALL SELECT 50
--UNION ALL SELECT 48
--UNION ALL SELECT 82
--UNION ALL SELECT 83
declare @i int
set @i=1
while @i<=100
begin
INSERT @t select @i
set @i=@i+1
end

DECLARE @tt TABLE(ida int,a int,idb int,b int,idc int,c int)
DECLARE @result TABLE(a int,b int,c int)

insert into @tt
select A.id,A.value,B.id,B.value,C.id,C.value from
@t A,
@t B,
(select id,value from @t
union
select 0 id,0 value ) C
where A.id>B.id and B.id>C.id 
and (A.value+B.value+C.value)>=98
and (A.value+B.value+C.value)<=102
--上面找出可能的所有组合，但存在重复
declare @ida int,@idb int,@idc int
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by newid()
insert into @result select a,b,c from @tt where ida=@ida and idb=@idb and idc=@idc

while @@rowcount>0
begin
delete from @tt where 
ida=@ida or idb=@ida or idc=@ida or ida=@idb or idb=@idb or idc=@idb 
or (ida=@idc and @idc<>0) or (idb=@idc and @idc<>0) or (idc=@idc and @idc<>0)
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by newid()
insert into @result select a,b,c from @tt where ida=@ida and idb=@idb and idc=@idc
end
--上面随机找出符合的组合
--select * from @result order by c,b,a
insert into @Aresult select @j,a,b,c from @result 
delete from @t
delete from @tt
delete from @result
--的得出结果
set @j=@j+1
end 
declare @z int 
select top 1 @z=id from @Aresult group by id order by count(1)
select a,b,c from @Aresult where id=@z order by c,b,a
--可能的话可以提高循环的次数--结果a           b           c           
----------- ----------- ----------- 
74          24          0
65          36          0
60          38          0
57          42          0
58          44          0
55          45          0
51          47          0
53          48          0
87          13          1
64          32          2
91          7           3
86          12          4
79          14          5
73          23          6
78          16          8
69          22          9
52          37          10
54          33          11
59          25          15
56          28          17
41          40          18
49          30          19
50          29          20
46          34          21
43          31          26
39          35          27（所影响的行数为 26 行）

Answer 5

--测试
--有兴趣的朋友可以实验下下面的代码,100次循环大概50秒的时间
declare @Aresult table(id int,a int,b int,c int)
declare @j int
set @j=1
set nocount on
while @j<=100
begin
DECLARE @t TABLE(id int identity(1,1),value int)
--INSERT @t SELECT 39
--UNION ALL SELECT 40
--UNION ALL SELECT 5
--UNION ALL SELECT 55
--UNION ALL SELECT 17
--UNION ALL SELECT 17
--UNION ALL SELECT 50
--UNION ALL SELECT 48
--UNION ALL SELECT 82
--UNION ALL SELECT 83
declare @i int
set @i=1
while @i<=100
begin
INSERT @t select @i
set @i=@i+1
end
--构建模拟数据

DECLARE @tt TABLE(ida int,a int,idb int,b int,idc int,c int)
DECLARE @result TABLE(a int,b int,c int)

insert into @tt
select A.id,A.value,B.id,B.value,C.id,C.value from
@t A,
@t B,
(select id,value from @t
union
select 0 id,0 value ) C
where A.id>B.id and B.id>C.id 
and (A.value+B.value+C.value)>=98
and (A.value+B.value+C.value)<=102
--上面找出可能的所有组合，但存在重复
declare @ida int,@idb int,@idc int
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by newid()
insert into @result select a,b,c from @tt where ida=@ida and idb=@idb and idc=@idc

while @@rowcount>0
begin
delete from @tt where 
ida=@ida or idb=@ida or idc=@ida or ida=@idb or idb=@idb or idc=@idb 
or (ida=@idc and @idc<>0) or (idb=@idc and @idc<>0) or (idc=@idc and @idc<>0)
--删除和选出记录冲突的记录
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by newid()
insert into @result select a,b,c from @tt where ida=@ida and idb=@idb and idc=@idc
end
--上面随机找出符合的组合
--select * from @result order by c,b,a
insert into @Aresult select @j,a,b,c from @result 
delete from @t
delete from @tt
delete from @result
set @j=@j+1
--准备下一次尝试
end 
set nocount off
declare @z int 
select top 1 @z=id from @Aresult group by id order by count(1) desc
select '('+rtrim(a)+','+rtrim(b)+case c when 0 then ')' else ','+rtrim(c)+')' end 组合 from @Aresult where id=@z order by c,b,a
--找出N次循环后的最优结果
组合                                       
---------------------------------------- 
(100,1)
(77,24)
(76,25)
(74,26)
(71,27)
(69,32)
(68,33)
(66,34)
(65,37)
(63,39)
(58,40)
(60,41)
(54,44)
(53,45)
(56,46)
(52,48)
(67,30,2)
(55,42,3)
(92,6,4)
(59,38,5)
(83,12,7)
(70,23,8)
(61,31,9)
(75,17,10)
(72,15,11)
(57,29,13)
(51,35,14)
(64,18,16)
(62,20,19)
(50,28,21)
(43,36,22)（所影响的行数为 31 行）
--因为找不到好的算法才做扫描，还可以根据自己的判断做倾向性扫描，次数越多，越接近真实答案

Answer 6

这更多的是一道数学题,为什么一定要用SQL来处理,有什么实际意义吗?

Answer 7

--产生一组数据
create TABLE #t(
id int identity, 
value int)declare @i int
set @i=0
declare @tt int
while @i <100
begin
   set @tt=cast(rand()*100 as int)
   while @tt=0
      set @tt=cast(rand()*100 as int)
   insert #t values(@tt)
   set @i=@i+1
end
--显示数据
select * from #t--产生所有组合
declare @t table(
id int identity, 
id1 int,
id2 int,
id3 int,
value int
)--两两
insert @t
select a.id as id1,b.id as id2,null,a.value+b.value as value
from #t a,#t b
where a.id<b.id
and a.value+b.value between 98 and 102--三组合
insert @t
select a.id as id1,b.id as id2,c.id as id3,a.value+b.value+c.value as value
from #t a,#t b,#t c
where a.id<b.id
and b.id<c.id
and a.value+b.value+c.value between 98 and 102--查看组合
select * from @t--很难找出最多的组合，不过如果先尽量多的找两两组合，总的组合数应该多些
declare @r table(
id int, 
id1 int,
id2 int,
id3 int,
value int
)--先找两两组合
insert into @r 
select top 1 * from @t where id3 is null order by newid()
while @@rowcount>0
begin
delete t
from @t t,@r r 
where t.id1=r.id1
or t.id1=r.id2
or t.id1=r.id3
or t.id2=r.id1
or t.id2=r.id2
or t.id2=r.id3
or t.id3=r.id1
or t.id3=r.id2
or t.id3=r.id3
insert into @r 
select top 1 * from @t where id3 is null order by newid()
end--再找三组合
insert into @r 
select top 1 * from @t order by newid()while @@rowcount>0
begin
delete t
from @t t,@r r 
where t.id1=r.id1
or t.id1=r.id2
or t.id1=r.id3
or t.id2=r.id1
or t.id2=r.id2
or t.id2=r.id3
or t.id3=r.id1
or t.id3=r.id2
or t.id3=r.id3insert into @r 
select top 1 * from @t order by newid()
end--显示结果，一般都有40-45个组合
select * from @r--显示未加入组合的数据
select * from #t
where id not in (
select id1 from @r
union all
select id2 from @r
union all
select id3 from @r where id3 is not null
)

Answer 8

--修改下
declare @Aresult table(id int,a int,b int,c int)
declare @j int
set @j=1
set nocount on
while @j<=1
begin
DECLARE @t TABLE(id int identity(1,1),value int)
--INSERT @t SELECT 39
--UNION ALL SELECT 40
--UNION ALL SELECT 5
--UNION ALL SELECT 55
--UNION ALL SELECT 17
--UNION ALL SELECT 17
--UNION ALL SELECT 50
--UNION ALL SELECT 48
--UNION ALL SELECT 82
--UNION ALL SELECT 83
declare @i int
set @i=1
while @i<=100
begin
INSERT @t select @i
set @i=@i+1
end
--构建模拟数据

DECLARE @tt TABLE(ida int,a int,idb int,b int,idc int,c int)
DECLARE @result TABLE(a int,b int,c int)

insert into @tt
select A.id,A.value,B.id,B.value,C.id,C.value from
@t A,
@t B,
(select id,value from @t
union
select 0 id,0 value ) C
where A.id>B.id and B.id>C.id 
and (A.value+B.value+C.value)>=98
and (A.value+B.value+C.value)<=102
--上面找出可能的所有组合，但存在重复
--select * from @tt
declare @ida int,@idb int,@idc int
if exists(select 1 from @tt where @idc=0)
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt where @idc=0 order by  ida - idb desc
else
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by a desc,b desc
insert into @result select a,b,c from @tt where ida=@ida and idb=@idb and idc=@idc

while @@rowcount>0
begin
delete from @tt where 
ida=@ida or idb=@ida or idc=@ida or ida=@idb or idb=@idb or idc=@idb 
or (ida=@idc and @idc<>0) or (idb=@idc and @idc<>0) or (idc=@idc and @idc<>0)
--删除和选出记录冲突的记录
if exists(select 1 from @tt where @idc=0)
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt where @idc=0 order by ida - idb desc
else
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by a desc,b desc
insert into @result select a,b,c from @tt where ida=@ida and idb=@idb and idc=@idc
end
--上面随机找出符合的组合
--select * from @result order by c,b,a
insert into @Aresult select @j,a,b,c from @result 
delete from @t
delete from @tt
delete from @result
set @j=@j+1
--准备下一次尝试
end 
set nocount off
declare @z int 
select top 1 @z=id from @Aresult group by id order by count(1) desc
select '('+rtrim(a)+','+rtrim(b)+case c when 0 then ')' else ','+rtrim(c)+')' end 组合 from @Aresult where id=@z order by c,b,a
--找出N次循环后的最优结果
组合                                       
---------------------------------------- 
(99,1)
(100,2)
(98,3)
(97,4)
(96,5)
(95,6)
(94,7)
(93,8)
(92,9)
(91,10)
(90,11)
(89,12)
(88,13)
(87,14)
(86,15)
(85,16)
(84,17)
(83,18)
(82,19)
(81,20)
(80,21)
(79,22)
(78,23)
(77,24)
(76,25)
(75,26)
(74,27)
(73,28)
(72,29)
(71,30)
(70,31)
(69,32)
(68,33)
(67,34)
(66,35)
(65,36)
(64,37)
(63,38)
(62,39)
(61,40)
(60,41)
(59,42)
(58,43)
(57,44)
(56,45)
(55,46)
(54,47)
(53,48)
(52,49)
(51,50)（所影响的行数为 50 行）

Answer 9

if exists(select 1 from @tt where @idc=0)
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt where @idc=0 order by  ida - idb desc
else
select top 1 @ida=ida,@idb=idb,@idc=idc from @tt order by a desc,b desc
加了这个就多了，但只是针对这一特殊类型数据，也就是说选择有个倾向性，
但实际的数据可能不适合这样处理，问题在于如何找才能找到最优（是和现有的数据关联的）

Answer 10

楼主不好意思。借你的人气发个帖子，恳请高手帮忙看看我的问题：
超级郁闷！SQL Server 不存在或访问被拒绝！！ 
http://community.csdn.net/Expert/topic/5025/5025209.xml?temp=7.549465E-03

Answer 11

如果以组合的个数最多为标准，CSDMN有更好的解决方法吗？我的算法中, 去掉 三次组合中的下面这个处理条件.
AND NOT EXISTS(
SELECT * FROM #1 
WHERE flag = 1 
AND B.id in(A.id1, A.id2))
)A然后把游标循环的处理按组合数字的个数(可以直接在缓存中间结果的表中加标志字段)倒排序就行了.

Answer 12

-- 也就是改成这样就可以了, 100条数据在我的电脑中, 一样是3秒可以出来了.-- 测试数据, value 列放你要处理的数
DECLARE @t TABLE(
id int identity, 
value int)
INSERT @t SELECT TOP 100 ABS(CHECKSUM(NEWID())) % 100 FROM syscolumns-- 组合处理
DECLARE @r TABLE(
id int identity, 
ids varchar(100), 
vs varchar(100))
DECLARE @tid TABLE(id varchar(10))SELECT 
id1 = A.id, value1 = A.value,
id2 = B.id, value2 = B.value,
value = A.value + B.value,
flag = CASE WHEN A.value + B.value BETWEEN 98 AND 102 THEN 1 ELSE 0 END
INTO #1
FROM @t A, @t B
WHERE A.id < B.idDECLARE tb CURSOR STATIC LOCAL
FOR
SELECT ids = ',' + ids + ',', vs
FROM(
-- 二次组合的
SELECT flag = 2,
ids  = RTRIM(A.id1) + ',' + RTRIM(A.id2), 
vs = RTRIM(A.value1) + ',' + RTRIM(A.value2)
FROM #1 A
WHERE flag = 1
UNION ALL
-- 三次组合的
SELECT flag = 3,
RTRIM(A.id1) + ',' + RTRIM(A.id2) + ',' + RTRIM(B.ID),
RTRIM(A.value1) + ',' + RTRIM(A.value2) + ',' + RTRIM(B.value)
--SELECT A.value1, A.value2, B.value
FROM #1 A, @t B
WHERE A.id2 < B.id
AND A.flag = 0
AND A.value + B.value BETWEEN 98 AND 102
--AND NOT EXISTS(
--SELECT * FROM #1 
--WHERE flag = 1 
--AND B.id in(A.id1, A.id2))
)A
ORDER BY flag DESCDECLARE @ids varchar(100), @values varchar(100)
OPEN tb
FETCH tb INTO @ids, @values
WHILE @@ROWCOUNT > 0
BEGIN
IF NOT EXISTS(
SELECT * FROM @tid WHERE CHARINDEX(id, @ids) > 0)
BEGIN
INSERT @r VALUES(@ids, @values)
INSERT @tid SELECT ',' + RTRIM(id) + ',' FROM @t
WHERE CHARINDEX(',' + RTRIM(id) + ',', @ids) > 0
END
FETCH tb INTO @ids, @values
END
CLOSE tb
DEALLOCATE tbSELECT vs FROM @r
GODROP TABLE #1

Answer 13

-- 改进了游标处理方法, 1秒就可以出结果了. 如果你都是大于0的数, 还可以直接加过滤条件来减少数据处理量.-- 测试数据, value 列放你要处理的数
DECLARE @t TABLE(
id int identity, 
value int)
INSERT @t SELECT TOP 100 CHECKSUM(NEWID()) % 100 FROM syscolumns--=====================================================
-- 组合处理
--=====================================================
DECLARE @r TABLE(
id int IDENTITY, 
vs varchar(100))
DECLARE @tid TABLE(id int PRIMARY KEY)IF OBJECT_ID('tempdb..#1') IS NOT NULL
DROP TABLE #1
SELECT 
id1 = A.id, value1 = A.value,
id2 = B.id, value2 = B.value,
value = A.value + B.value,
flag = CASE WHEN A.value + B.value BETWEEN 98 AND 102 THEN 1 ELSE 0 END
INTO #1
FROM @t A, @t B
WHERE A.id < B.idDECLARE tb CURSOR STATIC LOCAL
FOR
SELECT id1, id2, id3, vs
FROM(
-- 二次组合的
SELECT flag = 2,
A.id1, A.id2, id3 = NULL,
vs = RTRIM(A.value1) + ',' + RTRIM(A.value2)
FROM #1 A
WHERE flag = 1
UNION ALL
-- 三次组合的
SELECT flag = 3,
A.id1, A.id2, id3 = B.id,
RTRIM(A.value1) + ',' + RTRIM(A.value2) + ',' + RTRIM(B.value)
FROM #1 A, @t B
WHERE A.id2 < B.id
AND A.value + B.value BETWEEN 98 AND 102
)A
ORDER BY flag DESCDECLARE @id1 int, @id2 int, @id3 int, @values varchar(100)
OPEN tb
FETCH tb INTO @id1, @id2, @id3, @values
WHILE @@ROWCOUNT > 0
BEGIN
IF NOT EXISTS(
SELECT * FROM @tid WHERE id IN(@id1, @id2, @id3))
BEGIN
INSERT @r VALUES(@values)
INSERT @tid SELECT *
FROM(
SELECT id = @id1 UNION ALL SELECT @id2 UNION ALL SELECT @id3
)A WHERE id > 0
END
FETCH tb INTO @id1, @id2, @id3, @values
END
CLOSE tb
DEALLOCATE tbSELECT vs FROM @r