最优逼近算法-用SP实现

Question

现有装箱表declare @T table (name varchar(10),volume decimal(9,2))insert @T select '1','6.24'
union select '3','8.96'
union select '4','8.10'
union select '5','4.37'
union select '6','10.56'
union select '7','50.89'
...
union select '120','21.69'
...name是货名，volume是货物的体积
表T中有N行货物，实际数在100左右
运输货物的集装箱为68立方米
要求：用存储过程实现的算法来输出一份最大限度利用集装箱空间的货物单

Answer 1

redwoodschu
    哪来的题啊....真牛X

Answer 2

问题在于这样最优的算法会导致一些单位体积较小的货物会一直不被选中，只能通过人工来解决另外一般优化都是用二叉排序树，在MSSQL里如何实现类似二叉数这种外部程序语言的函数呢

Answer 3

用while回答我
(60 5)   (32 30)   (50 3 ) 
和
(60 5 3)  (32 30)   (50 )
你想要哪中排法~~~
还是没要求~只要不多出个组合就可以了

Answer 4

create table tt(name varchar(10),volume decimal(9,2))
insert tt select '1','6.24'
union select '3','8.96'
union select '4','8.10'
union select '5','4.37'
union select '6','10.56'
union select '7','50.89'
select * into # from tt 
create table #sql(coid int identity(1,1), co varchar(2000))declare @int decimal(9,2),@sql varchar(2000),@sqldelete varchar(100)
select @int=max(volume) from # where volume<=68while(exists(select 1 from # where volume<=68))
begin
select top 1 @sql=name
from # where volume in(select max(volume) from # where volume<=@int)delete # where name=@sql while(exists(select 1 from # where volume<=68-@int))
begin
select @int=@int+max(volume) from # where volume<=68-@int
select top 1 @sql=@sql+','+name,@sqldelete=name
from # where volume in(select max(volume) from # where volume<=68)
delete # where name=@sqldelete
endinsert into #sql values(@sql)
select @int=max(volume) from # where volume<=68
endselect * from #sql
drop table #
drop table #sql
--明天再优化一下~~今天先回了...

Answer 5

--OK了~~改天优化~~
create table tt(name varchar(10),volume decimal(9,2))
insert tt select '1','6.24'
union select '3','8.96'
union select '4','8.10'
union select '5','4.37'
union select '6','10.56'
union select '7','50.89'
union select '8','6.24'
union select '9','8.96'
union select '10','8.10'
union select '11','4.37'
union select '12','10.56'
union select '13','50.89'
select * into # from tt where volume<=68
create table #sql(coid int identity(1,1), co varchar(2000))declare @int decimal(9,2),@max int,@sql varchar(2000),@sqldelete varchar(100)
select @int=max(volume) from #while(exists(select 1 from #))
begin
select top 1 @sql=name,@sqldelete=name
from # where volume in(select max(volume) from #)delete # where name=@sqldelete while(exists(select 1 from # where volume<=68-@int))
begin
set @max=68-@int
select @int=@int+max(volume) from # where volume<=@max select top 1 @sql=@sql+','+name,@sqldelete=name
from # where volume in(select max(volume) from # where volume<=@max) delete # where name=@sqldelete
endinsert into #sql values(@sql)
select @int=max(volume) from # where volume<=68
endselect * from #sqlselect a.*,b.coid from tt a left join #sql b on CHARINDEX(','+a.name+',',','+b.co+',')>0
order by b.coiddrop table #
drop table #sql

Answer 6

谢谢w75251455(砍破)
粗略看了下，还是通过选择一个最小的体积足够大的货物，依次递归下去的算法
其实用这个算法的话一张用临时表就可以了，一个DOWHILE循环就可以了

Answer 7

感觉在数据库里做这么复杂的实现，效果不好，还是把数据读到C#的数组里，用C#来完成好了
我先试试，不行就去C#那边请教，嘿嘿。。

Answer 8

第一:我没用递归...
第二:不是从最小的~~是最大的~~
第三:也不是依次下去~~~是<=68-@max
第四:我可以不用临时表!!!!!!!只要你不介意我在你表上多加个列...

Answer 9

to : w75251455(砍破)手上没有环境,测不了砍破的..如果集装箱是10立方米
货特如下:
name1 2立方米
name2 5立方米
name3 5立方米
name4 9立方米这种情况选择的是name2和name3 
不知道你的算法是否涉及到?

Answer 10

第一:我没用递归...
－－－－－－
楼主说的递规也可以写成循环。第二:不是从最小的~~是最大的~~
－－－－－－－－－－
楼主说的最小的体积足够大的货物是指小于当前可用空间的最大的。第三:也不是依次下去~~~是<=68-@max
－－－－－－－－－－－－－－－－－
楼主也是这个意思。第四:我可以不用临时表!!!!!!!只要你不介意我在你表上多加个列...
－－－－－－－－－
我没看你的写法，但觉得你的算法跟楼主是一个意思。

Answer 11

谢谢w75251455(砍破)
粗略看了下，还是通过选择一个最小的体积足够大的货物，依次递归下去的算法
其实用这个算法的话一张用临时表就可以了，一个DOWHILE循环就可以了
---------------------------------------------------------------------------------
还是通过选择一个最小的体积足够大的货物(错错错错..这样做不出来)
mengmou()mengmou() 不知道你有没有想这个算法~~

Answer 12

to: mengmou()mengmou() 
还是通过选择一个最小的体积足够大的货物，依次递归下去的算法
(用这种思路又想了一下~~~觉得出来的数据是不正确的~~~)

Answer 13

我们都是学生~~~永远都是学生~~~现在是csdn的学生~~~
觉得有个学生比你学得好一点~~~你应该想.怎么跟上~~~
怎么可以用<真牛>带过``

Answer 14

谢谢showlin(六斤八两八) 帮我说话...
LZ说的简单逼近~是有到理的~~~可LZ说的实现过程是有问题的!!

Answer 15

DROP TABLE t
--思路,按体积正向排序成#2,排逆向排序为#1,
CREATE TABLE t
(
name varchar(10),
volume decimal(9,2)
)
GO
INSERT INTO t 
select '1',6.24
union select '3',8.96
union select '4',8.10
union select '5',4.37
union select '6',10.56
union select '7',50.89
union select '13',18.96
union select '14',34
union select '15',34
union select '16',34
union select '16',34
union select '17',50.89
go
CREATE TABLE #1
(
id int identity(1,1),
name varchar(10),
volume decimal(9,2)
)
go
CREATE TABLE #2
(
id int identity(1,1),
name varchar(10),
volume decimal(9,2),
id1 int
)
go
declare @t1row int,@t2row int,@cnt int,@t1volume int ,@t2volume int,@id1 int,@id2 int
insert into #1(name,volume) select name, volume from t order by volume desc
insert into #2(name,volume) select name, volume from t order by volume
set @cnt=@@rowcount
set @t1row =1
set @t2row =1
--外层循环,按#1id选择体积从大到小的记录
while @t1row<@cntbegin
select @id1=id,@t1volume=volume from #1 where id=@t1row
--内层循环,选出id<行总数-#t1总数的行,从小到大sum,当小于等于68-#1对应的体积时,更新id1为#1的id
while @t2row<=@cnt-@t1row
begin
if (select ISNULL(sum(volume),0) from #2 where id <=@t2row AND id1 IS NULL)<=68-@t1volume
BEGIN
set @t2row=@t2row+1
END
else
BEGIN
update #2 set id1=@id1 WHERE ID<@t2row AND id1 IS NULL
BREAK
END
end
update #2 set id1=@id1 WHERE ID<@t2row AND id1 IS NULL
SET @t1row=@t1row+1
end
--选择出符合#2中id1=#1中id值的记录,group by 所有列,将奇数列中间可能重复的值排除.
SELECT * FROM (
select ID,name ,volume from #1 WHERE ID IN(SELECT id1 FROM #2) UNION ALL
SELECT ID1 AS ID,name ,volume from #2 WHERE NOT ID1 IS NULL) A
GROUP BY ID,name,volume
ORDER BY ID
drop table #1,#2--结果可按id相同的装车
ID          name       volume
----------- ---------- ---------------------------------------
1           1          6.24
1           17         50.89
1           5          4.37
2           3          8.96
2           4          8.10
2           7          50.89
3           13         18.96
3           16         34.00
3           6          10.56
4           14         34.00(10 行受影响)

Answer 16

select a.*,b.coid from tt a left join #sql b on CHARINDEX(','+a.name+',',','+b.co+',')>0
order by b.coid
这样搞一下~只是为了让别人好理解...
select * from #sql
报表是这个....

Answer 17

以前写着玩的一段代码。，，在大家也就看着玩玩继续关注。/*
为实现库存自动预留而想出的取卷算法。
以分到卷的布料为例，取卷方法：
1、以最大数量的卷开始取
2、以最大数量的卷开始取后的余数就取数量最小的卷
*/
SET NOCOUNT ONCREATE TABLE #Roll_Qty(sRollNo INT IDENTITY(1,1), fOnHandQty DECIMAL(9,2))
GO
INSERT INTO #Roll_Qty VALUES(100)
INSERT INTO #Roll_Qty VALUES(100)
INSERT INTO #Roll_Qty VALUES(100)
INSERT INTO #Roll_Qty VALUES(100)
INSERT INTO #Roll_Qty VALUES(80)
INSERT INTO #Roll_Qty VALUES(50)
INSERT INTO #Roll_Qty VALUES(30)
INSERT INTO #Roll_Qty VALUES(20)
INSERT INTO #Roll_Qty VALUES(20)
INSERT INTO #Roll_Qty VALUES(10)
INSERT INTO #Roll_Qty VALUES(10)
INSERT INTO #Roll_Qty VALUES(2.3)
INSERT INTO #Roll_Qty VALUES(2.3)
INSERT INTO #Roll_Qty VALUES(2.3)
INSERT INTO #Roll_Qty VALUES(2.2)
INSERT INTO #Roll_Qty VALUES(2.1)
GO
--@fSumQty 要取得的总数量
--@ftmpQty 用于计算当前所有取得的卷号的当前总数量，前当总数量不能大于总数量
--@iCount 为当前总数量的卷数
--@fCurQty 当前所能取的卷号的数量。
--@bIsCan 这里用于判断如果总数量＜当前总数量＋fOnHandQty　则@bIsCan为0（不再处理）
DECLARE @fSumQty DECIMAL(12,2), @ftmpQty DECIMAL(12,2), @iCount INT, @fCurQty DECIMAL(12,2), @bIsCan BITSELECT @fSumQty = 403.1,  --要预留的数量
@ftmpQty = 0, @iCount = 0, @fCurQty = 0, @bIsCan = 1--如果总数量大于#Roll_Qty的总数量则退出
IF @fSumQty > (SELECT SUM(fOnHandQty) FROM #Roll_Qty)
BEGIN
    DROP TABLE #Roll_Qty    RAISERROR('数量超出！', 16, 1)    RETURN
ENDSELECT
    --如果@bIsCan为0则退出
    @bIsCan = CASE @bIsCan WHEN 1 THEN CASE WHEN @ftmpQty + fOnHandQty < @fSumQty THEN 1 ELSE 0 END ELSE 0 END,
    --判断如果总数量＜当前总数量＋下一卷数量　则Select无效(@ftmpQty + @fCurQty < @fSumQty永远不成立)
    @fCurQty = CASE WHEN (@bIsCan = 1) AND @ftmpQty + fOnHandQty < @fSumQty THEN fOnHandQty ELSE @fCurQty END,
    --记录汇总到当前的总卷数
    @iCount = @iCount + CASE WHEN (@bIsCan = 1) AND @ftmpQty + @fCurQty < @fSumQty THEN 1 ELSE 0 END,
    --记录汇总到当前的各卷的总数量
    @ftmpQty = @ftmpQty + CASE WHEN (@bIsCan = 1) AND @ftmpQty + @fCurQty < @fSumQty THEN fOnHandQty ELSE 0 END
FROM #Roll_Qty
WHERE fOnHandQty > 0
AND @bIsCan = 1--可去掉，对效率没什么影响
ORDER BY fOnHandQty DESCCREATE TABLE #tmp_Roll_Qty(sRollNo VARCHAR(20) PRIMARY KEY, fOnHandQty DECIMAL(9,2))--取出总数为@ftmpQty（当前总数量）的卷
INSERT INTO #tmp_Roll_Qty
EXEC('SELECT TOP ' + @iCount + ' sRollNo, fOnHandQty FROM #Roll_Qty ORDER BY fOnHandQty DESC')SET NOCOUNT OFFSELECT *
FROM (
--从最大的开始取
    SELECT sRollNo,  fOnHandQty
    FROM #tmp_Roll_Qty
    UNION
--取得后一卷
    --取出@fSumQty（总数量）－@ftmpQty（当前总数量）之后数量最接近的卷
    SELECT TOP 1 sRollNo, fOnHandQty
    FROM #Roll_Qty
    WHERE fOnHandQty >= @fSumQty - @ftmpQty
        AND sRollNo NOT IN (SELECT sRollNo FROM #tmp_Roll_Qty)
    ORDER BY fOnHandQty
    ) a
ORDER BY sRollNoDROP TABLE #tmp_Roll_QtyDROP TABLE #Roll_QtySELECT @fSumQty, @ftmpQty, @iCount

Answer 18

declare @T table (name varchar(10),volume decimal(9,2))
insert @T select '1','6.24'
union select '3','8.96'
union select '4','8.10'
union select '5','4.37'
union select '6','10.56'
union select '7','50.89'
union select '120','21.69'
----集装箱体积
declare @Vol decimal(9,2)
set @Vol=68
----集装箱货物名称
declare @name varchar(8000)
set @name=''
----实际装的体积
declare @Tmp decimal(9,2)
set @Tmp=0select @name=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @name+name+',' else @name end,
@Tmp=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @Tmp+volume else @Tmp end
from @T
order by volume descprint @name---结果  7,6,1,

Answer 19

kadboy(kadboy)
我以前怎么没想到这种用变量方式呢~~呵呵~
以后我会常用的...

Answer 20

变量这东西很好用的。。看来代码太长没人看。。从事数据库工作是指DBA吗？

Answer 21

DROP TABLE t
--思路,按体积正向排序成#2,排逆向排序为#1,
CREATE TABLE t
(
name varchar(10),
volume decimal(9,2)
)
GO
INSERT INTO t 
select '1',6.24
union select '3',8.96
union select '4',8.10
union select '5',4.37
union select '6',10.56
union select '7',50.89
union select '13',18.96
union select '14',34
union select '15',34
union select '16',34
union select '17',50.89
union select '27',67.9
union select '28',67.9
go
CREATE TABLE #1
(
id int identity(1,1),
name varchar(10),
volume decimal(9,2)
)
go
CREATE TABLE #2
(
id int identity(1,1),
name varchar(10),
volume decimal(9,2),
id1 int
)
go
declare @t1row int,@t2row int,@cnt int,@t1volume int ,@t2volume int,@id1 int,@id2 int
insert into #1(name,volume) select name, volume from t order by volume desc,name desc
insert into #2(name,volume) select name, volume from t order by volume,name
set @cnt=@@rowcount
set @t1row =1
set @t2row =1
--外层循环,按#1id选择体积从大到小的记录
while @t1row<@cntbegin
select @id1=id,@t1volume=volume from #1 where id=@t1row
--内层循环,选出id<行总数-#t1总数的行,从小到大sum,当小于等于68-#1对应的体积时,更新id1为#1的id
while @t2row<=@cnt-@t1row
begin
if (select ISNULL(sum(volume),0) from #2 where id <=@t2row AND id1 IS NULL)<=68-@t1volume
BEGIN
set @t2row=@t2row+1
END
else
BEGIN
update #2 set id1=@id1 WHERE ID<@t2row AND id1 IS NULL
BREAK
END
end
update #2 set id1=@id1 WHERE ID<@t2row AND id1 IS NULL
SET @t1row=@t1row+1
end
--选择出符合#2中id1=#1中id值的记录,group by 所有列,将奇数列中间可能重复的值排除.
SELECT * FROM (
SELECT ID,name ,volume FROM #1 WHERE ID IN(SELECT id1 FROM #2) UNION ALL
SELECT ID1 AS ID,name ,volume FROM #2 WHERE NOT ID1 IS NULL  UNION ALL
SELECT ID,name ,volume FROM #1 WHERE  NOT EXISTS(SELECT 1 FROM #2 WHERE id1=#1.ID) AND (SELECT COUNT(1) FROM #2 WHERE ID=@cnt-#1.ID AND ID1 IS NULL)=1
) A
GROUP BY ID,name,volume
ORDER BY ID
drop table #1,#2
--刚才的忘记了最大值没有一个可以与它相加小于等于68的
--结果
ID          name       volume
----------- ---------- ---------------------------------------
1           28         67.90
2           27         67.90
3           1          6.24
3           5          4.37
3           7          50.89
4           17         50.89
4           3          8.96
4           4          8.10
5           13         18.96
5           16         34.00
5           6          10.56
6           14         34.00
6           15         34.00(13 行受影响)

Answer 22

递归“从剩下的货物中选择出不大于货箱剩余空间的最大一件装入”
9,9,5,5,3,3,2,1
组合结果就是
9,1
9
5,5
3,3,2这不就是楼主原来的意思？简单逼近而已。貌似这就够用了---------------------------------------------------同意showlin(六斤八两八) 的说法
最优是相对的，5,5和9,1，哪个是最优，程序员不需要知道，这是业务员的事
程序员要做的是，把符合最优条件的集合PROGRAM出来

Answer 23

kadboy(kadboy) 
有前途啊~~我在用你的办法~~对我上面的语句优化(代码长度上的..)...

Answer 24

SQL2005不是可以用C#来做SP么，如果用C#实现了，不知道编译出来的SQL语言是怎么样的
真想看看啊

Answer 25

create table tt(name varchar(10),volume decimal(9,2))
insert tt select '1','6.24'
union select '3','8.96'
union select '4','8.10'
union select '5','4.37'
union select '6','10.56'
union select '7','50.89'
union select '8','6.24'
union select '9','8.96'
union select '10','8.10'
union select '11','4.37'
union select '12','10.56'
union select '13','50.89'select * into # from tt where volume<=68 order by volume desc
create table #sql(coid int identity(1,1), co varchar(2000),[托运合计] decimal(9,2))while(exists(select 1 from #))
begin
----集装箱体积
declare @Vol decimal(9,2)
set @Vol=68
----集装箱货物名称
declare @name varchar(8000)
set @name=''
----实际装的体积
declare @Tmp decimal(9,2)
set @Tmp=0select @name=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @name+name+',' else @name end,
@Tmp=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @Tmp+volume else @Tmp end
from #declare @dec dec(9,2)
select @dec=sum(volume) from # where CHARINDEX(','+name+',' ,','+@name)>0
insert into #sql values(@name,@dec)
delete from # where CHARINDEX(','+name+',' ,','+@name)>0
endselect * from #sqldrop table #sql
drop table #

Answer 26

coid     co                  托运合计
1        13,6,1,             67.69
2        7,12,8,             67.69
3        3,9,4,10,11,5,      42.86

Answer 27

select * into # from tt where volume<=68 order by volume desc
create table #sql(coid int identity(1,1), co varchar(2000),[托运合计] decimal(9,2))while(exists(select 1 from #))
begin
----集装箱体积
declare @Vol decimal(9,2)
set @Vol=68
----集装箱货物名称
declare @name varchar(8000)
set @name=''
----实际装的体积
declare @Tmp decimal(9,2)
set @Tmp=0
----托运合计
declare @TmpSum decimal(9,2)
set @TmpSum=0select @name=case when @Vol-@Tmp>=volume
then @name+name+',' else @name end,
@Tmp=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @Tmp+volume else @Tmp end
from #
insert into #sql values(@name,@Tmp)
delete from # where CHARINDEX(','+name+',' ,','+@name)>0
endselect * from #sqldrop table #sql
drop table #
--人都快傻了....
/*
coid     co                  托运合计
1        13,6,1,             67.69
2        7,12,8,             67.69
3        3,9,4,10,11,5,      42.86
*/

Answer 28

select @name=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @name+name+',' else @name end,
@Tmp=case when @Tmp<@Vol and @Vol-@Tmp>=volume
then @Tmp+volume else @Tmp end这个确实有新意阿，对于用惯了DOIFLESEWHILE的来说

Answer 29

这个还是用数据库好，数据库相关编程前台代码多了自然不好迁移语种和C/S与B/S迁移。既然数据库后面有个Server就要充分利用。就只是用循环和临时表难度不大

Answer 30

w75251455(砍破) ( ) 信誉：100    Blog  2007-3-15 14:46:28  得分: 0  
 
 
   
kadboy(kadboy) 
有前途啊~~我在用你的办法~~对我上面的语句优化(代码长度上的..)... ------------------------- 
 
两位兄弟有创意