最优逼近算法-用SP实现
现有装箱表
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立方米
要求：用存储过程实现的算法来输出一份最大限度利用集装箱空间的货物单
[解决办法]
redwoodschu
哪来的题啊....真牛X
[解决办法]
简单逼近很好做，就是选择一个最小的体积足够大的货物，依次递归下去
这个不是挺好吗？
[解决办法]
呵呵，又现高手！
[解决办法]
to : w75251455(砍破)
手上没有环境,测不了砍破的..
如果集装箱是10立方米
货特如下:
name1 2立方米
name2 5立方米
name3 5立方米
name4 9立方米
这种情况选择的是name2和name3
不知道你的算法是否涉及到?
[解决办法]
第一:我没用递归...
－－－－－－
楼主说的递规也可以写成循环。
第二:不是从最小的~~是最大的~~
－－－－－－－－－－
楼主说的最小的体积足够大的货物是指小于当前可用空间的最大的。
第三:也不是依次下去~~~是 <=68-@max
－－－－－－－－－－－－－－－－－
楼主也是这个意思。
第四:我可以不用临时表!!!!!!!只要你不介意我在你表上多加个列...
－－－－－－－－－
我没看你的写法，但觉得你的算法跟楼主是一个意思。
[解决办法]
砍破真牛,我也顶一下
[解决办法]
up
[解决办法]
UP
[解决办法]
递归“从剩下的货物中选择出不大于货箱剩余空间的最大一件装入”
9,9,5,5,3,3,2,1
组合结果就是
9,1
9
5,5
3,3,2
这不就是楼主原来的意思？简单逼近而已。貌似这就够用了
[解决办法]
up
[解决办法]
用贪婪法行吗？
9,9,5,5,3,3,2,2,1 如果集装箱是10
组合结果：
9,1
[解决办法]
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 <@cnt
begin
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 行受影响)
[解决办法]
请问一下，把上面的算法用到数据量几万的表上效率怎样？
[解决办法]
以前写着玩的一段代码。，，在大家也就看着玩玩。。。继续关注。。。。
/*
为实现库存自动预留而想出的取卷算法。
以分到卷的布料为例，取卷方法：
1、以最大数量的卷开始取
2、以最大数量的卷开始取后的余数就取数量最小的卷
*/
SET NOCOUNT ON
CREATE 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 BIT
SELECT @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
END
SELECT
--如果@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 DESC
CREATE 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 OFF
SELECT *
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 sRollNo
DROP TABLE #tmp_Roll_Qty
DROP TABLE #Roll_Qty
SELECT @fSumQty, @ftmpQty, @iCount
[解决办法]
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=0
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
from @T
order by volume desc
print @name
---结果 7,6,1,
[解决办法]
mark
[解决办法]
背包原理啊
[解决办法]
(60 5) (32 30) (50 3 )
(60 5 3) (32 30) (50 )
个人认为后一种,
这是你现在所有的货物,
假设你用第一种,当你装完第一箱时,又来了一个18的货物,你只能排到下一箱去了.
[解决办法]
学习`````!!
