Pau*_*mes 12 sql-server query sql-server-2014
我将用尽可能均匀地装载固定数量的卡车订单来描述问题。
输入：
@TruckCount - the number of empty trucks to fill
一套：
OrderId,
OrderDetailId,
OrderDetailSize,
TruckId (initially null)
Orders由一个或多个组成OrderDetails。
这里的挑战是TruckId为每条记录分配一个。
单个订单不能跨卡车拆分。
卡车应尽可能均匀*装载，以sum(OrderDetailSize).
* 均匀：装载最少的卡车和装载最多的卡车之间可实现的最小增量。根据这个定义，1,2,3 比 1,1,4 分布更均匀。如果有帮助，请假装您是统计算法，创建均匀的高度直方图。
没有考虑最大卡车负载。这些是神奇的弹性卡车。然而，卡车的数量是固定的。
有一个明显的迭代解决方案 - 循环分配订单。
但是它可以作为基于集合的逻辑来完成吗？
我的主要兴趣是 SQL Server 2014 或更高版本。但其他平台的基于集合的解决方案也可能很有趣。
这感觉就像 Itzik Ben-Gan 领土 :)
我的实际应用程序将处理工作负载分配到多个存储桶中，以匹配逻辑 CPU 的数量。因此每个桶没有最大大小。统计更新，特别是。我只是认为将问题抽象为卡车作为构建挑战的一种方式会更有趣。
CREATE TABLE #OrderDetail (
OrderId int NOT NULL,
OrderDetailId int NOT NULL PRIMARY KEY,
OrderDetailSize tinyint NOT NULL,
TruckId tinyint NULL)
-- Sample Data
INSERT #OrderDetail (OrderId, OrderDetailId, OrderDetailSize)
VALUES
(1 ,100 ,75 ),
(2 ,101 ,5 ),
(2 ,102 ,5 ),
(2 ,103 ,5 ),
(2 ,104 ,5 ),
(2 ,105 ,5 ),
(3 ,106 ,100),
(4 ,107 ,1 ),
(5 ,108 ,11 ),
(6 ,109 ,21 ),
(7 ,110 ,49 ),
(8 ,111 ,25 ),
(8 ,112 ,25 ),
(9 ,113 ,40 ),
(10 ,114 ,49 ),
(11 ,115 ,10 ),
(11 ,116 ,10 ),
(12 ,117 ,15 ),
(13 ,118 ,18 ),
(14 ,119 ,26 )
--> YOUR SOLUTION HERE
-- After assigning Trucks, Measure delta between most and least loaded trucks.
-- Zero is perfect score, however the challenge is a set based solution that will scale, and produce good results, rather
-- than iterative solution that will produce perfect results by exploring every possibility.
SELECT max(TruckOrderDetailSize) - MIN(TruckOrderDetailSize) AS TruckMinMaxDelta
FROM
(SELECT SUM(OrderDetailSize) AS TruckOrderDetailSize FROM #OrderDetail GROUP BY TruckId) AS Truck
DROP TABLE #OrderDetail
我的第一个想法是
select
<best solution>
from
<all possible combinations>
问题中定义了“最佳解决方案”部分 - 装载最多和装载最少的卡车之间的最小差异。另一点——所有的组合——让我停下来思考。
考虑我们有三个订单 A、B 和 C 以及三辆卡车的情况。可能性是
Truck 1 Truck 2 Truck 3
------- ------- -------
A B C
A C B
B A C
B C A
C A B
C B A
AB C -
AB - C
C AB -
- AB C
C - AB
- C AB
AC B -
AC - B
B AC -
- AC B
B - AC
- B AC
BC A -
BC - A
A BC -
- BC A
A - BC
- A BC
ABC - -
- ABC -
- - ABC
Table A: all permutations.
其中许多是对称的。例如，前六行的区别仅在于每个订单放置在哪辆卡车上。由于卡车是可互换的，因此这些安排将产生相同的结果。我暂时忽略这一点。
存在用于产生排列和组合的已知查询。但是，这些将在单个存储桶内产生排列。对于这个问题，我需要跨多个存储桶进行安排。
查看标准“所有组合”查询的输出
;with Numbers as
(
select n = 1
union
select 2
union
select 3
)
select
a.n,
b.n,
c.n
from Numbers as a
cross join Numbers as b
cross join Numbers as c
order by 1, 2, 3;
n n n
--- --- ---
1 1 1
1 1 2
1 1 3
1 2 1
<snip>
3 2 3
3 3 1
3 3 2
3 3 3
Table B: cross join of three values.
我注意到，结果形成相同的图形表A.通过使每一个考虑的认知飞跃柱是一个令1，该值的说这车会认为订单和排是卡车内的订单的安排。查询然后变成
select
Arrangement = ROW_NUMBER() over(order by (select null)),
First_order_goes_in = a.TruckNumber,
Second_order_goes_in = b.TruckNumber,
Third_order_goes_in = c.TruckNumber
from Trucks a -- aka Numbers in Table B
cross join Trucks b
cross join Trucks c
Arrangement First_order_goes_in Second_order_goes_in Third_order_goes_in
----------- ------------------- -------------------- -------------------
1 1 1 1
2 1 1 2
3 1 1 3
4 1 2 1
<snip>
Query C: Orders in trucks.
扩展它以涵盖示例数据中的 14 个订单，并简化我们得到的名称：
;with Trucks as
(
select *
from (values (1), (2), (3)) as T(TruckNumber)
)
select
arrangement = ROW_NUMBER() over(order by (select null)),
First = a.TruckNumber,
Second = b.TruckNumber,
Third = c.TruckNumber,
Fourth = d.TruckNumber,
Fifth = e.TruckNumber,
Sixth = f.TruckNumber,
Seventh = g.TruckNumber,
Eigth = h.TruckNumber,
Ninth = i.TruckNumber,
Tenth = j.TruckNumber,
Eleventh = k.TruckNumber,
Twelth = l.TruckNumber,
Thirteenth = m.TruckNumber,
Fourteenth = n.TruckNumber
into #Arrangements
from Trucks a
cross join Trucks b
cross join Trucks c
cross join Trucks d
cross join Trucks e
cross join Trucks f
cross join Trucks g
cross join Trucks h
cross join Trucks i
cross join Trucks j
cross join Trucks k
cross join Trucks l
cross join Trucks m
cross join Trucks n;
Query D: Orders spread over trucks.
为方便起见，我选择将中间结果保存在临时表中。
如果数据首先是 UNPIVOTED，后续步骤会容易得多。
select
Arrangement,
TruckNumber,
ItemNumber = case NewColumn
when 'First' then 1
when 'Second' then 2
when 'Third' then 3
when 'Fourth' then 4
when 'Fifth' then 5
when 'Sixth' then 6
when 'Seventh' then 7
when 'Eigth' then 8
when 'Ninth' then 9
when 'Tenth' then 10
when 'Eleventh' then 11
when 'Twelth' then 12
when 'Thirteenth' then 13
when 'Fourteenth' then 14
else -1
end
into #FilledTrucks
from #Arrangements
unpivot
(
TruckNumber
for NewColumn IN
(
First,
Second,
Third,
Fourth,
Fifth,
Sixth,
Seventh,
Eigth,
Ninth,
Tenth,
Eleventh,
Twelth,
Thirteenth,
Fourteenth
)
) as q;
Query E: Filled trucks, unpivoted.
可以通过加入 Orders 表来引入权重。
select
ft.arrangement,
ft.TruckNumber,
TruckWeight = sum(i.Size)
into #TruckWeights
from #FilledTrucks as ft
inner join #Order as i
on i.OrderId = ft.ItemNumber
group by
ft.arrangement,
ft.TruckNumber;
Query F: truck weights
现在可以通过找到在最大载重和最小载重卡车之间具有最小差异的安排来回答这个问题
select
Arrangement,
LightestTruck = MIN(TruckWeight),
HeaviestTruck = MAX(TruckWeight),
Delta = MAX(TruckWeight) - MIN(TruckWeight)
from #TruckWeights
group by
arrangement
order by
4 ASC;
Query G: most balanced arrangements
这有很多问题。首先它是一个蛮力算法。工作表中的行数与卡车和订单的数量呈指数关系。#Arrangements 中的行数是（卡车数量）^（订单数量）。这不会很好地扩展。
其次是 SQL 查询中嵌入了订单数。解决这个问题的唯一方法是使用动态 SQL，它有其自身的问题。如果订单数以千计，那么生成的 SQL 可能会变得太长。
三是安排上的冗余。这会极大地增加中间表的运行时间。
第四，#Arrangements 中的许多行让一辆或多辆卡车空着。这不可能是最佳配置。在创建时过滤掉这些行会很容易。我选择不这样做是为了让代码更简单和专注。
从好的方面来说，这可以处理负权重，如果您的企业开始运送充满氦气的气球！
如果有一种方法可以直接从卡车和订单列表中填充 #FilledTrucks，我认为这些问题中最严重的问题是可以控制的。可悲的是，我的想象力在这个障碍上绊倒了。我希望未来的一些贡献者能够提供那些我没有想到的东西。
1您说订单的所有商品都必须在同一辆卡车上。这意味着赋值的原子是 Order，而不是 OrderDetail。我从您的测试数据中生成了这些：
select
OrderId,
Size = sum(OrderDetailSize)
into #Order
from #OrderDetail
group by OrderId;
但是，无论我们将有问题的项目标记为“订单”还是“订单详细信息”都没有区别，解决方案保持不变。
| 归档时间： |
|
| 查看次数： |
1768 次 |
| 最近记录： |