SQL query for FIFO allocation of items

Question

I have a real world business scenario but for the sake of clarity let me rephrase it as a simpler fictional problem.

We have Buyers and Items.

DECLARE @Buyer TABLE 
(
 BuyerId INT IDENTITY(1,1),
 Name NVARCHAR(100),
 Budget INT
);

INSERT @Buyer (Name, Budget) VALUES 
('Anna', 100),
('Brett', 50),
('Conor', 20)

DECLARE @Item TABLE
(
 ItemId INT IDENTITY(1,1),
 Cost INT
);

INSERT @Item (Cost) VALUES (50),(30),(20),(40),(10),(40),(30),(10),(5);

The goal is to craft a query (no loops or cursor) which allocates items to buyers, based on their budget. The most expensive items should be allocated in priority.

Expected result:

ItemId BuyerName  
1  Anna
4  Anna  
6  Brett
7  NULL  
2  NULL  
3  Conor  
5  Anna  
8  Brett
9, NULL  

From a logical perpective, this is what happens. First, the items are sorted by descending cost

ItemId Cost  
1   50  
4   40  
6   40  
7   30  
2   30  
3   20  
5   10  
8   10  
9   5  

Then we go through each item and try to allocate it to a buyer that has enough budget left.

• Item 1 => Can be assigned to Anna. Anna's remaining budget is 100 - 50 = 50
• Item 4 => Can be assigned to Anna. Anna's remaining budget is 50 - 40 = 10
• Item 6 => Can be assigned to Brett. Brett's remaining budget is 50 - 40 = 10
• Item 7 => No one has enough budget left
• Item 2 => No one has enough budget left
• Item 3 => Can be assigned to Conor. Conor's remaining budget is 20 - 20 = 0
• Item 5 => Can be assigned to Anna. Anna's remaining budget is 10 - 10 = 0
• Item 8 => Can be assigned to Brett. Brett's remaining budget is 10 - 10 = 0
• Item 9 => No one has enough budget left

Answer 1

Nasty, but will do what you wanted:

DECLARE @Out TABLE (BuyerId int, ItemId int);
DECLARE @BuyerId int, @Budget int, @ItemId int, @Cost int;

WHILE EXISTS(SELECT TOP 1 Budget FROM @Buyer WHERE Budget >= (SELECT MIN(Cost) FROM @Item))
BEGIN
    SELECT TOP 1 @BuyerId = BuyerId, @Budget = Budget
    FROM @Buyer
    WHERE Budget >= (SELECT MIN(Cost) FROM @Item)

    SELECT TOP 1 @ItemId = ItemId, @Cost = Cost 
    FROM @Item
    WHERE Cost <= @Budget
    ORDER BY Cost DESC, ItemId ASC;

    DELETE FROM @Item WHERE ItemId = @ItemId;
    UPDATE @Buyer SET Budget -= @Cost WHERE BuyerId = @BuyerId;
    INSERT INTO @Out VALUES(@BuyerId,@ItemId)
END
SELECT * FROM @Out

UPDATE (2020-10-16):

Based on OPs comment I decided to try to do as much as possible using set based data flow. First of all solution requires to create all possible permutations without duplicates where the order doesn't matter. For that I used a recursive CTE, then out of all possible price sums we needed only these in the Buyers budget, then I ordered them form the most expensive set (as asked by OP) where we want most expensive item first then the most expensive still in the budget and so on. I ended up with having the order column, JSON array for ItemId and all other base data:

;WITH totalCostPermutations AS(
SELECT 
ItemIndex = CAST(CONCAT('"',ItemId,'') as varchar(max)),
X = CAST(ROW_NUMBER() OVER (ORDER BY Cost DESC, ItemId ASC) as varchar(max)),
ItemId, Cost
FROM @Item
UNION ALL
SELECT
ItemIndex = CAST(CONCAT(i1.ItemIndex,'", "',i2.ItemId) as varchar(max)),
X = CONCAT(i1.X, ROW_NUMBER() OVER (ORDER BY i2.Cost DESC, i2.ItemId ASC)),
i2.ItemId, Cost = (i1.Cost + i2.Cost)
FROM totalCostPermutations i1
JOIN @Item i2 ON 1=1
AND i1.ItemId < i2.ItemId
)
SELECT
RN = ROW_NUMBER() OVER(PARTITION BY b.BuyerId ORDER BY Cost DESC, X ASC),
ItemId_JSON = CONCAT('{"ItemId":[',ItemIndex,'"]}'), TotalCost = Cost,  b.*
FROM totalCostPermutations c
JOIN @Buyer b ON c.Cost <= b.Budget;

At this stage our data looks like this:

But from this point I can't think of how could this be possible to tell which ItemId have already been "used" and which not, without looping. Still, from this output it won't be hard to either loop it in T-SQL or via the app.

Answer 2

This is incomplete, may be someone can finish it if possible.

DECLARE @Buyer TABLE 
(
 BuyerId INT IDENTITY(1,1),
 Name NVARCHAR(100),
 Budget INT
);

INSERT @Buyer (Name, Budget) VALUES 
('Anna', 100),
('Brett', 50),
('Conor', 20)

DECLARE @Item TABLE
(
 ItemId INT IDENTITY(1,1),
 Cost INT
);

INSERT @Item (Cost) VALUES (50),(30),(20),(40),(10),(40),(30),(10),(5);

--select *,lag(cost) over(order by cost desc)from @Item
--return
Declare @rn int,@rn1 int
select @rn=count(*) from @Buyer

select @rn1=count(*) from @Item

;with CTE1 as
(
select *,ROW_NUMBER()over(order by cost desc) rownum from  @Item 
)
,CTE as
(
select ItemId
, i.Cost
,BuyerId as rn 
, rownum rn1
,rownum
,b.Budget,
i.Cost as Totalcost
--,case when i.cost<=b.Budget then b.Name end Buyer,
,1 rn2
,case when b.Budget>=cost then 1 else 0 end Status

from CTE1 I
, @Buyer B
where rownum=1
and b.BuyerId=1

union all

select 
i.ItemId
,i.cost

,case when  t1.rn2/@rn1=rn then rn +1 else rn end
,case when I.rownum=@rn1 then 0 else rn1+1 end
,i.rownum
,b.Budget
,case 
when t1.rn2/@rn1=rn then i.Cost  
when b.Budget>= i.Cost+t1.Totalcost 
then i.Cost+t1.Totalcost else t1.Totalcost end   as Totalcost
--,case when i.cost+<=b.Budget then b.Name end Buyer
,rn2+1
,case when t1.rn2/@rn1=rn and b.Budget>=i.cost and t1.cost>0  then 1 
when b.Budget>= i.Cost+t1.Totalcost and t1.cost>0   then 1
else 0 end 

from CTE1 I 
inner join CTE t1 on I.rownum=rn1+1
, @Buyer B
--and rn1<=10
where  b.BuyerId=case when  t1.rn2/@rn1=rn then rn +1 else rn end 
and rn<=@rn



)

select * from CTE

Can we know CTE t1 old status when rn>1 ?

Answer 3

I think @mustaccio is right, the problem is a "knapsack problem".

You maybe can attack the problem the other way around using GROUP BY CUBE.

select coalesce(a, 0) + coalesce(b, 0) + coalesce(c, 0) + coalesce(d, 0) + coalesce(e, 0) + coalesce(f, 0) + coalesce(g, 0) + coalesce(h, 0) + coalesce(i, 0)
from (values (50, 30, 20, 40, 10, 40, 30, 10, 5)) t(a,b,c,d,e,f,g,h,i)
group by cube(a,b,c,d,e,f,g,h,i)
having (case when a is not null then 1 else 0 end +
        case when b is not null then 1 else 0 end +
        case when c is not null then 1 else 0 end +
        case when d is not null then 1 else 0 end +
        case when e is not null then 1 else 0 end +
        case when f is not null then 1 else 0 end +
        case when g is not null then 1 else 0 end +
        case when h is not null then 1 else 0 end +
        case when i is not null then 1 else 0 end
       ) = 3;

In this case I'm calculating all possible combinations of the SUM of 3 items.

Now that you have all possible totals you can see how those totals fit in your user's budget.

I know is not exactly what you wanted but I hope I might have give you new ideas.

Answer 4

aka bin packing

There is a recent article on solving this type of problem here :-

https://www.sqlservercentral.com/articles/a-set-based-solution-for-the-bin-packing-problem