sql问题 谁给个头绪

Question

快想办法，有好算法不愁分 就是求num的和必须小于10 ，而且尽量优化的组合，比如我给的数就2次足够了

Answer 1

1,3
2,5
3,4
4,1
5,4
6,2num值不能大于10，如果按id顺序取就是3-5  4-1-4   2分了3次，但其实2次就够了，象我举的例子，有好算法偶加分

Answer 2

你的意思是：将NUM进行分组，使得每组的和都小于10，求组数最小的分法。

Answer 3

1。如果存在大于10的数字，提示数据不符合要求。
2。递归：
   给出n个数，求取出m个数，使得m个数的和最大且小于等于10。
   另 n= n-m（剔除已经选取的m个数）
   循环递归
3。输出

Answer 4

熊 想想就难，我用c#循环着对比，慢的厉害，而且算法也不行herb2的说法是对的，按num进行分组，每组都小于或等于10

Answer 5

select id,num，(id + num) as summary from tb where summary<10select id,num，(id + num) as summary from tb where order by summary

Answer 6

恩，我算的是num列,
其实算哪列都可以

Answer 7

说实话,
现在头还是晕的,
昨天晚上看球,一宿没睡.
所以看到这个算法也晕了,
疯子讲详细点.
或者是我还没有睡醒.....
omg...

Answer 8

正在做，有点头绪了，
我+herb2解释的难道真都没看懂？日了举个不太恰当的例子，比如有：100个人，有100间房子，
要求每个房间的住的人的年龄总和不能大于1000岁，
要求尽量少的使用房间这能明白吗？

Answer 9

在你的原表上增加了一列标示列
set nocount on 
create table tb(id int,num int,bz int)
insert into tb select 1,3,0
insert into tb select 2,5,0
insert into tb select 3,4,0
insert into tb select 4,1,0
insert into tb select 5,4,0
insert into tb select 6,2,0
go
 declare @i int,@j int,@n int,@id varchar(200),@k int
 declare @t table(num int,c int,id varchar(200))
 select @k = 0
 while exists(select 1 from tb where bz = 0)
  begin 
   delete @t
   select @i = 2,@j = count(*),@n = 10 from tb where bz = 0
   insert @t select num,1,rtrim(id)+',' from tb where bz = 0
   while @i<=@j
    begin
     insert @t select a.num+b.num,2,a.id+rtrim(b.id)+',' from @t a,tb b where charindex(rtrim(b.id)+',',a.id)=0 and a.num+b.num <= @n and b.bz = 0
     select @i = @i +1
    end
   select top 1 @id = id,@k = @k + 1 from @t order by num desc 
   update tb set bz = @k where charindex(rtrim(id)+',',@id)> 0
  end
  select id,num,分组=bz from tb order by bz,id
go
drop table tb
/*
id          num         分组          
----------- ----------- ----------- 
          1           3           1 
          2           5           1 
          6           2           1 
          3           4           2 
          4           1           2 
          5           4           2 
*/

Answer 10

这个比上面的性能好点。
set nocount on 
create table tb(id int,num int,bz int)
insert into tb select 1,3,0
insert into tb select 2,5,0
insert into tb select 3,4,0
insert into tb select 4,1,0
insert into tb select 5,4,0
insert into tb select 6,2,0
go
 declare @i int,@j int,@n int,@id varchar(200),@k int
 declare @t table(num int,id varchar(200))
 select @i = 2,@j = count(*),@n = 10,@k = 0 from tb 
 insert @t select num,rtrim(id)+',' from tb 
 while @i<=@j
  begin
    insert @t select a.num+b.num,a.id+rtrim(b.id)+',' from @t a,tb b where charindex(rtrim(b.id)+',',a.id)=0 and a.num+b.num <= @n and b.bz = 0
    select @i = @i +1
  end
 while exists(select 1 from @t)
 begin
   select top 1 @id = id,@k = @k + 1 from @t order by num desc 
   update tb set bz = @k where charindex(rtrim(id)+',',@id)> 0
   delete a from @t a where exists(select 1 from tb where bz <> 0 and charindex(rtrim(id)+',',a.id)> 0)
 end 
 select id,num,分组=bz from tb order by bz,id
go
drop table tb
/*
id          num         分组          
----------- ----------- ----------- 
          1           3           1 
          2           5           1 
          6           2           1 
          3           4           2 
          4           1           2 
          5           4           2 
*/

Answer 11

天，这样还不明白，偶表达能力真不行哦 !herb2写完了，看看，偶的也快写挖了，谢谢

Answer 12

明白了，只是不好算。
最小组数应该等于sum(num)/10取整+1吧

Answer 13

这个是极限最优解，但实际数据可能得不到这个最优解。
实际上这就是一个N-P问题。
有一堆东西，每个都有重量，用袋子装这些东西，但每个袋子的承重是固定得，求一种装法，使用袋子最少。另：23楼有个小问题，不影响结果，但影响性能，修正如下：
 insert @t select num,1,rtrim(id)+',' from tb 
 while @i<=@j
  begin
    insert @t select a.num+b.num,@i,a.id+rtrim(b.id)+',' from @t a,tb b where charindex(rtrim(b.id)+',',a.id)=0 and a.num+b.num <= @n and a.c = @i - 1

Answer 14

还可以增加β剪枝
while @i <=@j and @@rowcount>0

Answer 15

呵呵 厉害，我还算取最大，然后取n个最小，>标准值就推出，小于则再找最小 汗...
先看看

Answer 16

二等草发个完整的看看
用这些数据：
create table tb(id int,num int,bz int)
insert into tb select 1,3,0
insert into tb select 2,5,0
insert into tb select 3,4,0
insert into tb select 4,1,0
insert into tb select 5,4,0
insert into tb select 6,3,0
insert into tb select 7,7,0
insert into tb select 8,4,0
insert into tb select 9,2,0
insert into tb select 10,9,0
insert into tb select 11,1,0
insert into tb select 12,9,0
insert into tb select 13,9,0

Answer 17

if object_id('tb') is not null
drop table tb
go
create table tb(id int identity(1,1),num int,[index] int)
declare @i int
set @i=10
while @i>0
begin
insert into tb(num) select cast(rand()*9 as int)+1
set @i=@i-1
enddeclare @max int,@maxid int,@maxnum int,@minid int,@minnum int,@index int
set @max=10
set @index=1while exists(select 1 from tb where [index] is null)
begin
select @maxnum=max(num) from tb where num<=@max and [index] is null 
select @maxid=id from tb where num=@maxnum and [index] is null order by newid()
update tb set [index]=@index where id=@maxid
while @maxnum<=@max
begin
select @minnum=min(num) from tb where [index] is null
select @minid=id from tb where num=@minnum and [index] is null order by newid()
if @maxnum+@minnum<=10 and @minnum is not null
begin

update tb set [index]=@index where id=@minid
set @maxnum=@maxnum+@minnum
end
else
break;
     end
set @index=@index+1
endselect * from tb order by [index]id num index
3 8 1
6 1 1
8 1 1
9 1 2
1 1 2
2 8 2
4 2 3
5 7 3
10 5 4
7 3 4我用的最大和最小取，优化程度我自己也不清楚，汗

Answer 18

完美厉害，有一个错误。
修正如下：
set nocount on 
create table tb(id int,num int,bz int) 
insert into tb select 1,3,0 
insert into tb select 2,5,0 
insert into tb select 3,4,0 
insert into tb select 4,1,0 
insert into tb select 5,4,0 
insert into tb select 6,3,0 
insert into tb select 7,7,0 
insert into tb select 8,4,0 
insert into tb select 9,2,0 
insert into tb select 10,9,0 
insert into tb select 11,1,0 
insert into tb select 12,9,0 
insert into tb select 13,9,0
go
 declare @i int,@j int,@n int,@id varchar(200),@k int
 declare @t table(num int,c int,id varchar(200))
 select @i = 2,@j = count(*),@n = 10,@k = 0 from tb 
 insert @t select num,1,','+rtrim(id)+',' from tb 
 while @i<=@j
  begin
    insert @t select a.num+b.num,@i,a.id+rtrim(b.id)+',' from @t a,tb b where charindex(','+rtrim(b.id)+',',a.id)=0 and a.num+b.num <= @n and a.c = @i - 1
    select @i = @i +1
  end
 while exists(select 1 from @t)
 begin
   select top 1 @id = id,@k = @k + 1 from @t order by num desc 
   update tb set bz = @k where charindex(','+rtrim(id)+',',@id)> 0
   delete a from @t a where exists(select 1 from tb where bz <> 0 and charindex(','+rtrim(id)+',',a.id)> 0)
 end 
 select id,num,分组=bz from tb order by bz,id
go
drop table tb
/*
id          num         分组          
----------- ----------- ----------- 
          1           3           1 
          7           7           1 
          4           1           2 
         10           9           2 
         11           1           3 
         12           9           3 
          2           5           4 
          6           3           4 
          9           2           4 
         13           9           5 
          3           4           6 
          5           4           6 
          8           4           7 
*/

Answer 19

if object_id('tb') is not null
drop table tb
go
create table tb(id int,num int,[index] int)
insert into tb select 1,3,null
insert into tb select 2,5,null
insert into tb select 3,4,null
insert into tb select 4,1,null
insert into tb select 5,4,null
insert into tb select 6,3,null
insert into tb select 7,7,null
insert into tb select 8,4,null
insert into tb select 9,2,null
insert into tb select 10,9,null
insert into tb select 11,1,null
insert into tb select 12,9,null
insert into tb select 13,9,nulldeclare @max int,@maxid int,@maxnum int,@minid int,@minnum int,@index int
set @max=10
set @index=1while exists(select 1 from tb where [index] is null)
begin
select @maxnum=max(num) from tb where num<=@max and [index] is null 
select @maxid=id from tb where num=@maxnum and [index] is null order by newid()
update tb set [index]=@index where id=@maxid
while @maxnum<=@max
begin
select @minnum=min(num) from tb where [index] is null
select @minid=id from tb where num=@minnum and [index] is null order by newid()
if @maxnum+@minnum<=10 and @minnum is not null
begin

update tb set [index]=@index where id=@minid
set @maxnum=@maxnum+@minnum
end
else
break;
     end
set @index=@index+1
endselect * from tb order by [index]id num index
11 1 1
13 9 1
12 9 2
4 1 2
10 9 3
9 2 4
7 7 4
6 3 5
2 5 5
1 3 6
8 4 6
3 4 7
5 4 7