我向 OP 提出了以下问题:查询的主要目标是什么?将“部件”分配给垃圾箱,以使每个垃圾箱包含相同数量的部件,尽可能多 - 无论每个垃圾箱中的开放天数如何?还是尽可能地平衡各个箱子的开放天数,即使这意味着一些箱子将接收更多零件(但每个箱子的开放天数较少)?显然,这两个目标是相互矛盾的。这两个问题是不同的。
OP还没有回答。但是后一个问题很有趣,无论哪种方式都值得解决。
编辑 似乎我的问题(在原始问题下作为评论发布)已被删除。无论是谁做的,都没有留下任何解释。无论如何,上面复制了这个问题。 结束编辑
Gordon Linoff 提供了一种解决方案,可以使每个箱中的零件数量相等。在那个解决方案(和问题陈述,真的)中,输入中每一行的“开放日”计数绝对没有任何作用。这是一个微不足道的问题(两种可能的解释)。
困难的问题 - 尽可能均衡每个箱中的开放天数的总和 - 可以通过完整的枚举来解决(考虑所有可能的分配,选择最好的分配),但这很快就变得不切实际。一个人需要一个算法,一个人也可能需要接受一个“足够好”的解决方案,虽然相当好但也很实用(查询应该在不到一年的时间内完成,例如,对于中等大的输入数据集)。
这是这样一个算法,然后是 Oracle SQL 中的一个实现——使用递归 WITH 子句,这需要 Oracle 11.2 或更高版本。
从三个箱子开始,按“开放日”降序排列“零件”。以任何方式通过“开放日”打破关系——这并不重要,但必须打破关系。ROW_NUMBER()
在初步子查询中,使用分析功能很容易。
跟踪每个 bin SO FAR 的总开放天数。(在我们开始之前,每个箱中的总数为零。)在每个步骤中,取出下一部分(按 排序ROW_NUMBER()
)并将其分配给当前开放天数总和最少的箱。如果存在平局,则优先选择 bin 1,然后是 bin 2,而不是其他 bin。
这是查询和结果 - 使用 CTE(在 WITH 子句中)中的输入数据进行测试。
with
tblso (part, opendays) as (
select 'ABB52', 203 from dual union all
select 'ABB85', 52 from dual union all
select 'ABB88', 365 from dual union all
select 'ABB26', 311 from dual union all
select 'ABB75', 288 from dual union all
select 'ABB92', 98 from dual union all
select 'ABB36', 113 from dual union all
select 'ABB37', 77 from dual union all
select 'ABB73', 297 from dual
)
, prep (part, opendays, rn) as (
select part, opendays, row_number() over (order by opendays desc) from tblso
)
, r (part, opendays, rn, bin, sum1, sum2, sum3) as (
select part, opendays, 1, 1, opendays, 0, 0
from prep
where rn = 1
union all
select p.part, p.opendays, p.rn,
case when r.sum1 <= r.sum2 and r.sum1 <= r.sum3 then 1
when r.sum2 <= r.sum3 then 2
else 3 end,
case when r.sum1 <= r.sum2 and r.sum1 <= r.sum3 then r.sum1 + p.opendays
else r.sum1 end,
case when r.sum2 < r.sum1 and r.sum2 <= r.sum3 then r.sum2 + p.opendays
else r.sum2 end,
case when r.sum3 < r.sum1 and r.sum3 < r.sum2 then r.sum3 + p.opendays
else r.sum3 end
from prep p join r on p.rn = r.rn + 1
)
select part, opendays, bin
from r;
输出:
PART OPENDAYS BIN
----- ---------- ----------
ABB88 365 1
ABB26 311 2
ABB73 297 3
ABB75 288 3
ABB52 203 2
ABB36 113 1
ABB92 98 1
ABB37 77 2
ABB85 52 1
为了比较,以下是 Gordon 答案中解决方案的“部分”计数和“开放日”总和,与此答案中的查询:
总帐摘要
BIN PART_COUNT TOTAL_OPENDAYS
---------- ---------- --------------
0 3 973
1 3 604
2 3 227
数学人总结
BIN PART_COUNT TOTAL_OPENDAYS
---------- ---------- --------------
1 4 628
2 3 591
3 2 585
Gordon 的解决方案将九个输入部分中的三个分配给三个箱中的每一个,但每个箱的总开放日范围从 227 到 973。在我的解决方案中,一个箱有四个部分,另一个只有两个;但每个垃圾箱的总开放天数从 585 到 628 不等 - 分布更紧密。
虽然不能保证,一般来说,我在这里描述的算法会找到最佳解决方案(要清楚:解决难题),几乎可以肯定,它会找到比分配相同数量的“部分”更好的解决方案几乎所有情况下的每个垃圾箱。