Distribute large quantities over multiple rows

Question

I have a simple Order table and one order can have different products with Quantity and it's Product's weight as below

OrderID	ProductName	Qty	Weight
101	ProductA	2	24
101	ProductB	1	24
101	ProductC	1	48
101	ProductD	1	12
101	ProductE	1	12
102	ProductA	5	60
102	ProductB	1	12

I am trying to partition and group the products in such a way that for an order, grouped products weight should not exceed 48.

Expected table look as below

OrderID	ProductName	Qty	Weight	GroupedID
101	ProductA	2	24	1
101	ProductB	1	24	1
101	ProductC	1	48	2
101	ProductD	1	12	3
101	ProductE	1	12	3
102	ProductA	4	48	1
102	ProductA	1	12	2
102	ProductB	1	12	2

Kindly let me know if this is possible.

Thank you.

Answer 1

This is a bin packing problem which is non-trivial in general. It's not just NP-complete but superexponential, ie the time increase as complexity increases is worse than exponential. Dai posted a link to Hugo Kornelis's article series which is referenced by everyone trying to solve this problem. The set-based solution performs really bad. For realistic scenarios you need iteration and preferably, using bin packing libraries eg in Python.

For production work it would be better to take advantage of SQL Server 2017+'s support for Python scripts and use a bin packing library like Google's OR Tools or the binpacking module. Even if you don't want to use sp_execute_external_script you can use a Python script to read the data from the database and split them.

The question's numbers are so regular though you could cheat a bit (actually quite a lot) and distribute all order lines into individual items, calculate the running total per order and then divide the total by the limit to produce the group number.

This works only because the running totals are guaranteed to align with the bin size.

Distributing into items can be done using a Tally/Numbers table, a table with a single Number column storing numbers from 0 to eg 1M.

Given the question's data:

declare @OrderItems table(id int identity(1,1) primary key, OrderID int,ProductName varchar(20),Qty int,Weight int)

insert into @OrderItems(OrderId,ProductName,Qty,Weight)
values
(101,'ProductA',2,24),
(101,'ProductB',1,24),
(101,'ProductC',1,48),
(101,'ProductD',1,12),
(101,'ProductE',1,12),
(102,'ProductA',5,60),
(102,'ProductB',1,12);

The following query will split each order item into individual items. It repeats each order item row as there are individual items and calculates the individual item weight

select o.*, Weight/Qty as ItemWeight
from @OrderItems o inner join Numbers ON Qty >Numbers.Number;

This row:

1   101 ProductA    2   24

Becomes

1   101 ProductA    2   24  12
1   101 ProductA    2   24  12

Calculating the running total inside a query can be done with :

SUM(ItemWeight) OVER(Partition By OrderId 
             Order By Itemweight
             ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)

The Order By Itemweight claus means the smallest items are picked first, ie it's a Worst fit algorithm.

The overall query calculating the total and Group ID is

with items as (
    select o.*, Weight/Qty as ItemWeight
    from @OrderItems o INNER JOIN Numbers ON Qty > Numbers.Number
)
select  Id,OrderId,ProductName,Qty,Weight, ItemWeight,
       ceiling(SUM(ItemWeight) OVER(Partition By OrderId 
             Order By Itemweight
             ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)/48.0) 
       As GroupId
from items;

After that, individual items need to be grouped back into order items and groups. This produces the final query:

with items as (
    select o.*, Weight/Qty as ItemWeight
    from @OrderItems o INNER JOIN Numbers ON Qty > Numbers.Number
)
,bins as(
    select  Id,OrderId,ProductName,Qty,Weight, ItemWeight,
       ceiling(SUM(ItemWeight) OVER(Partition By OrderId 
             Order By Itemweight
             ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)/48.0) As GroupId
    from items
)
select 
    max(OrderId) as orderid,
    max(productname) as ProductName,
    count(*) as Qty,
    sum(ItemWeight) as Weight, 
    max(GroupId) as GroupId
from bins
group by id,groupid
order by orderid,groupid

This returns

orderid	ProductName	Qty	Weight	GroupId
101	ProductA	2	24	1
101	ProductD	1	12	1
101	ProductE	1	12	1
101	ProductB	1	24	2
101	ProductC	1	48	3
102	ProductA	4	48	1
102	ProductA	1	12	2
102	ProductB	1	12	2