200分求数字组合算法

jenhon 2009-11-09 10:51:15

假设已知一个数集，已经排序好：
id num
1 2
2 3
3 3
4 5
6 7
7 12
8 23
....

指定一个较大的数，找出这个数集里的若干个数，使到这些数的和最接近这个指定的数。
2个要求：
1、尽可能接近，等于而不超过指定数；
2、符合要求的数字子集存在多个时，取包含最多数的子集。

比如指定的数是 15，最好的结果是：
id num
2 3
4 5
6 7

不过能算出：
id num
2 3
7 12
也可以考虑给分。

比如指定的数是 7，返回
id num
1 2
4 5

比如指定的数是 16，因为数集的数无法加出16的和，找最（小于）接近、包含的数最多的组合：
id num
2 3
4 5
6 7

200分求实现的算法或sql 语句。

本贴100 有答案另开贴给分。

（现实中我碰到的问题，数集是浮点数....唉，问题只能一步一步来了）

...全文

524 38 打赏收藏转发到动态举报

写回复

用AI写文章

38 条回复

切换为时间正序

请发表友善的回复…

发表回复

jenhon 2009-11-13

打赏
举报

啊？

jenhon 2009-11-12

打赏
举报

顶顶

jenhon 2009-11-10

打赏
举报

liangCK 也来帮忙啊~~~~

我想我需要的是我说的那种算法。

我的情况是这样：

少量的0~1的浮点数，大量（几万） 1~10 以内的浮点数，少量的10~100，极少的100~2000，
抽取数总和一般为30000到20万。

如果按照我说的那种情况抽取，100~2000极可能抽取不到（这个是允许）。
我的想法，就是希望能整片抽取，快速靠近，然后后面又能细化的逼近。

chuifengde 2009-11-10

打赏
举报

要快，可以改一下:

SET NOCOUNT ON 

DECLARE @n INT,@i INT 

DECLARE @m INT  

DECLARE @a TABLE(a VARCHAR(1000),b INT,c int)

DECLARE @b TABLE(a VARCHAR(1000),b INT,c int)

SET @n=100



INSERT @a SELECT *,null FROM yzs WHERE num<@n+1

INSERT @b SELECT * FROM @a  



SELECT @m=@@ROWCOUNT



SET @i=1

WHILE @i<=@m

BEGIN

	

    INSERT @a SELECT a.a+','+b.a,a.b+b.b,LEN(a.a+','+b.a)-LEN(REPLACE(a.a+','+b.a,',','')) FROM @a a ,@b b 

    WHERE CHARINDEX(','+b.a+',',','+a.a+',')=0 AND a.b+b.b<=@n

    DELETE FROM @a WHERE c<(SELECT MAX(c) FROM @a)

    SET @i=@i+1

END



SELECT distinct y.* FROM yzs y  

INNER JOIN (SELECT TOP 1 a FROM @a ORDER BY b+ISNULL(c,0) DESC)aa

on CHARINDEX(','+LTRIM(ID)+',',','+a+',')>0





--512M内存n=100时7秒出结果

luoyoumou 2009-11-10

打赏
举报

----楼主，别结帖早了，我来搞定！

jenhon 2009-11-10

打赏
举报

liangCK 我说的意思，不知道看得明白吗？

jenhon 2009-11-10

打赏
举报

感谢chuifengde的认真，可是8行数据，7秒我还是觉得有点慢，谢谢了。

liangCK 老大，我碰到的问题是几万条记录去抽取几千条到1、2万条记录，昨晚拿到你的算法之后，信心满满，弄了2000条记录，算了20多分钟日记溢出中止，削减到500条还是出错，100条还是不行，最后60条终于可以出结果了。可是总记录数60条才能干活，有点少啊。

工作的要求是不要超过、尽可能接近指定数值。

我原先的想法就是从头开始累加，累加到超过就停止，减回最后一个加上去的大数，结果就不会超过，但是这个数因为在后面，误差可能很大；
后来的想法，就是不减最大的数了，换成减最小的数，减到满足条件，这样的误差同样也可能很大，但误差大的可能性会随着抽样的数量变大而减小。
现在的想法，是第二步后，继续减过头，然后再从小数开始加回来...

liangCK 帮忙实现我说的这种算法的语句行吗？

bancxc 2009-11-09

打赏
举报

fc创一个我们学习学习
不是不想创新是我创不出来
[Quote=引用 14 楼 fcuandy 的回复:]
老问题，解法也是抄的，现在都没人搞创新？
[/Quote]

chkaka 2009-11-09

打赏
举报

IF OBJECT_ID('[tb]') IS NOT NULL DROP TABLE [tb]
CREATE TABLE [tb] (id int,num int)
INSERT INTO [tb]
SELECT 1,2 UNION ALL
SELECT 2,3 UNION ALL
SELECT 3,3 UNION ALL
SELECT 4,5 UNION ALL
SELECT 6,7 UNION ALL
SELECT 7,12 UNION ALL
SELECT 8,23
DECLARE @i int;
SET @i = 15;
select id,num from tb
where sum(num)<=i and max(count(*))

fcuandy 2009-11-09

打赏
举报

老问题，解法也是抄的，现在都没人搞创新？

忆轩辕 2009-11-09

打赏
举报

不在乎性能可以考虑一个循环，用一个变量，从第一个开始，如果加起来小于预期值则加上，如果加起来大于预期了则跳出循环，返回变量

bancxc 2009-11-09

打赏
举报



---不厚道了 学习梁哥的 对了的话分给梁哥

-------------------------------------

--  Author : liangCK 梁爱兰

--  Comment: 小梁 爱 兰儿

--  Date   : 2009-11-09 10:58:53

-------------------------------------

 

--> 生成测试数据: [tb]

IF OBJECT_ID('[tb]') IS NOT NULL DROP TABLE [tb]

CREATE TABLE [tb] (id int,num int)

INSERT INTO [tb]

SELECT 1,2 UNION ALL

SELECT 2,3 UNION ALL

SELECT 3,3 UNION ALL

SELECT 4,5 UNION ALL

SELECT 6,7 UNION ALL

SELECT 7,12 UNION ALL

SELECT 8,23



--SQL查询如下:



DECLARE @i int;

SET @i = 15;



;WITH Liang AS

(

    SELECT Plen=1 ,id,num,total=num,path=CAST(RTRIM(id) AS varchar(MAX))

    FROM tb WHERE num <= @i

    UNION ALL

    SELECT Plen=Plen+1,A.id,A.num,A.num+B.total,B.path+','+RTRIM(A.id)

    FROM tb AS A

        JOIN Liang AS B

    ON A.num+B.total <= @i AND A.id > B.id

        AND CHARINDEX(','+RTRIM(A.id)+',',','+B.path+',')=0

)

, cte as 

(

SELECT TOP 1 WITH TIES * FROM Liang WHERE total<=@i ORDER BY total DESC 

)



select * from cte where Plen=(select MAX(Plen) from cte)

/*

Plen        id          num         total       path

----------- ----------- ----------- ----------- -----------

4           6           7           15          1,2,3,6



(1 行受影响)

*/

bancxc 2009-11-09

打赏
举报

楼猪跑了

liangCK 2009-11-09

打赏
举报

包含数最多是什么意思?

liangCK 2009-11-09

打赏
举报

-------------------------------------

--  Author : liangCK 梁爱兰

--  Comment: 小梁 爱 兰儿

--  Date   : 2009-11-09 10:58:53

-------------------------------------

 

--> 生成测试数据: [tb]

IF OBJECT_ID('[tb]') IS NOT NULL DROP TABLE [tb]

CREATE TABLE [tb] (id int,num int)

INSERT INTO [tb]

SELECT 1,2 UNION ALL

SELECT 2,3 UNION ALL

SELECT 3,3 UNION ALL

SELECT 4,5 UNION ALL

SELECT 6,7 UNION ALL

SELECT 7,12 UNION ALL

SELECT 8,23



--SQL查询如下:



DECLARE @i int;

SET @i = 16;



;WITH Liang AS

(

    SELECT id,num,total=num,path=CAST(RTRIM(id) AS varchar(MAX)) 

    FROM tb WHERE num <= @i

    UNION ALL

    SELECT A.id,A.num,A.num+B.total,B.path+','+RTRIM(A.id)

    FROM tb AS A

        JOIN Liang AS B

    ON A.num+B.total <= @i AND A.id > B.id

        AND CHARINDEX(','+RTRIM(A.id)+',',','+B.path+',')=0

)

SELECT TOP 1 WITH TIES * FROM Liang WHERE total<=@i ORDER BY total DESC



/*

id          num         total       path

----------- ----------- ----------- -------------

7           12          15          3,7

6           7           15          3,4,6

7           12          15          2,7

6           7           15          2,4,6

6           7           15          1,2,3,6



(5 行受影响)

*/