用于组合程序/背包的动态T-SQL方法 [英] Dynamic T-SQL approach for combinatorics/knapsack
问题描述
我想我的问题与背包问题有关，但是我真的不能为此提出解决方案：
I guess my question has to do with a variant of the knapsack problem, but I can't really come up with a solution for this:
假设您在五金店，需要购买21颗螺丝。
他们只提供袋装商品：
Let's say you are in a hardware store and need to buy 21 screws. They only offer them in bags:
- 袋X-16颗螺钉-每颗螺钉1.56 $-总计25 $
- 包Y-8个螺丝-每个螺丝2.25 $-18 $总计
- 包Z-4个螺丝-每个螺丝1.75 $-7 $总
现在，您必须弄清楚应该买哪个包，才能以最低的价格得到21颗（或更多！）螺丝。
Now you have to figure out which Bags you should buy to get your 21 screws (or more!) for the lowest possible price.
所以我得到的是一张桌子，上面有所有的袋子，还有一个变量来定义所需的数量。因此，我需要的是一个包含bagname和所需金额的表。
So what I got is a table with all the bags and a variable to define the required amount. What I need as a result should be a table with the bagname and the required amount.
不幸的是sqlfiddle断开了。但是至少这是示例数据：
Unfortunately sqlfiddle is down.. But at least here's the example data:
declare @bags table (id int, qty int, price decimal(19,4))
insert into @bags values
(10, 16, 25.00)
,(20, 8, 18.00)
,(30, 4, 7.00)
declare @ReqQty int = 21
非常感谢您的帮助！希望我们能解决这个问题，因为我需要使用此重要功能定制我们公司的ERP系统。
I really appreciate your help! Hope we can get this solved, as I need to customize our companys ERP System with this important function.
谢谢！
编辑：
我阅读了有关背包的整个Wikipedia文章，其中说：
溢出近似算法
可能会生成一个近似算法，我们可以稍微超出允许的重量限制。您可能希望至少获得与给定边界B一样高的总值，但是您可以超过权重限制...
目前，这种近似算法的解决方案未知。
所以我似乎最好使用贪婪算法而不是发明轮子吗？ ;）
So it seems I better use a greedy algorithm instead of inventig the wheel? ;)
推荐答案
这是一个可能的解决方案。我将看明天是否可以完成，因为现在已经快三点了。主要逻辑在那里。剩下要做的就是使用 prev_w 值进行追溯。只需跳回来（从 best_price 行开始），直到到达 w = 0 行。当前行的 w 与上一行的差为您提供了每一步要购买的袋子的大小。
Here is a possible solution. I will see if I can finish it tomorrow as it's almost 3 AM here now. The main logic is there. All that's left to be done is to trace back using the prev_w values. Just jump back (starting from the best_price row) till you reach the w=0 row. The differences between the ws of current and the previous row give you the size of the bag you have to buy at each step.
在您的示例中，解决方案的路线显然是：
w = 24，w = 8，w = 4，w = 0的意思是购买行李：16，4， 4.。
这3个行李袋的价格为$ 39。
In your example, the solution route obviously is:
"w=24, w=8, w=4, w=0" which translates "to buy bags: 16, 4, 4.".
These 3 bags cost $39.
此解决方案假定该人不会购买超过1000颗螺丝的
（这是@limit的用途）。
This solution assumes the person is not going to buy
more than 1000 screws (this is what @limit is there for).
脚本草稿：
-- use TEST;
declare @limit decimal(19,4);
set @limit = 1000;
create table #bags
(
id int primary key,
qty int,
price decimal(19,4),
unit_price decimal(19,4),
w int, -- weight
v decimal(19,4) -- value
);
insert into #bags(id, qty, price)
values
(10, 16, 25.00)
,(20, 8, 18.00)
,(30, 4, 7.00);
declare @ReqQty int;
set @ReqQty = 21;
update #bags set unit_price = price / ( 1.0 * qty );
update #bags set w = qty;
update #bags set v = -price;
select * From #bags;
create table #m(w int primary key, m int, prev_w int);
declare @w int;
set @w = 0;
while (@w<=@limit)
begin
insert into #m(w) values (@w);
set @w = @w + 1;
end;
update #m
set m = 0;
set @w = 1;
declare @x decimal(19,4);
declare @y decimal(19,4);
update m1
set
m1.m = 0
from #m m1
where
m1.w = 0;
while (@w<=@limit)
begin
select
@x = max(b.v + m2.m)
from
#m m1
join #bags b on m1.w >= b.w and m1.w = @w
join #m m2 on m2.w = m1.w-b.w;
select @y = min(m22.w) from
#m m11
join #bags bb on m11.w >= bb.w and m11.w = @w
join #m m22 on m22.w = m11.w-bb.w
where
(bb.v + m22.m) = ( @x );
update m1
set
m1.m = @x,
m1.prev_w = @y
from #m m1
where
m1.w = @w;
set @w = @w + 1;
end;
select * from #m;
select
-m1.m as best_price
from
#m m1
where
m1.w = (select min(m2.w) from #m m2 where m2.w >= @ReqQty and (m2.m is not null));
drop table #bags;
drop table #m;
脚本最终版本：
-- use TEST;
declare @limit decimal(19,4);
set @limit = 1000;
declare @ReqQty int;
set @ReqQty = 21;
create table #bags
(
id int primary key,
qty int,
price decimal(19,4),
unit_price decimal(19,4),
w int, -- weight
v decimal(19,4), -- value
reqAmount int,
CONSTRAINT UNQ_qty UNIQUE(qty)
);
insert into #bags(id, qty, price)
values
(10, 16, 25.00)
,(20, 7, 14.00)
,(30, 4, 7.00);
update #bags set unit_price = price / ( 1.0 * qty );
update #bags set w = qty;
update #bags set v = -price;
update #bags set reqAmount = 0;
-- Uncomment the next line when debugging!
-- select * From #bags;
create table #m(w int primary key, m int, prev_w int);
declare @w int;
set @w = 0;
while (@w<=@limit)
begin
insert into #m(w) values (@w);
set @w = @w + 1;
end;
update #m
set m = 0;
set @w = 1;
declare @x decimal(19,4);
declare @y decimal(19,4);
update m1
set
m1.m = 0
from #m m1
where
m1.w = 0;
while (@w<=@limit)
begin
select
@x = max(b.v + m2.m)
from
#m m1
join #bags b on m1.w >= b.w and m1.w = @w
join #m m2 on m2.w = m1.w-b.w;
select @y = min(m22.w) from
#m m11
join #bags bb on m11.w >= bb.w and m11.w = @w
join #m m22 on m22.w = m11.w-bb.w
where
(bb.v + m22.m) = ( @x );
update m1
set
m1.m = @x,
m1.prev_w = @y
from #m m1
where
m1.w = @w;
set @w = @w + 1;
end;
-- Uncomment the next line when debugging!
-- select * from #m;
declare @z int;
set @z = -1;
select
@x = -m1.m,
@y = m1.w ,
@z = m1.prev_w
from
#m m1
where
m1.w =
-- The next line contained a bug. It's fixed now.
-- (select min(m2.w) from #m m2 where m2.w >= @ReqQty and (m2.m is not null));
(
select top 1 best.w from
(
select m1.m, max(m1.w) as w
from
#m m1
where
m1.m is not null
group by m1.m
) best where best.w >= @ReqQty and best.w < 2 * @ReqQty
order by best.m desc
)
-- Uncomment the next line when debugging!
-- select * From #m m1 where m1.w = @y;
while (@y > 0)
begin
update #bags
set reqAmount = reqAmount + 1
where
qty = @y-@z;
select
@x = -m1.m,
@y = m1.w ,
@z = m1.prev_w
from
#m m1
where
m1.w = @z;
end;
select * from #bags;
select sum(price * reqAmount) as best_price
from #bags;
drop table #bags;
drop table #m;
这篇关于用于组合程序/背包的动态T-SQL方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
