3

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
8
  • Related – mustaccio Oct 7 '20 at 16:18
  • I don't see how this is related at all? – Clement Oct 8 '20 at 14:19
  • 2
    Both are variations of the "knapsack problem". – mustaccio Oct 8 '20 at 14:32
  • The first item worth 50 can be assigned to Anna or to Brett. Why did you choose Anna? Does it matter which buyer to choose, as long as his budget allows it? In other words, you have defined an order for processing the items. Do you have any order/preference for processing buyers? The order in which we choose items and buyers affect the overall result. The optimal solution for a knapsack problem may be tricky in SQL. Some variation of the greedy algorithm may be possible to implement in SQL. – Vladimir Baranov Oct 12 '20 at 22:15
  • @VladimirBaranov the order for buyer doesn't matter. Can you point me to this greedy algorithm solution you mentioned? – Clement Oct 13 '20 at 6:52
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:

enter image description here

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.

4
  • Thanks but I'm after a set-based solution with no loops. My apologies if that wasn't clear. – Clement Oct 14 '20 at 12:14
  • You can probably do a second recursive CTE on top of this, or a join to itself, pseudocode: WHERE C1.RN = C2.RN + 1 AND C2.ItemId_JSON's values are not in C1.ItemId_JSON's values. (Might be better off losing the JSON array, and keeping each item ID in its own row for this purpose.) – J.D. Oct 19 '20 at 11:38
  • 1
    Agree, that or JOIN driven by dynamic SQL to determinate how many buyers there are. I wanted to do it as far as the solution feels elegant. From this point I can bet that the best performance will be to just simply read it line by line - simply loop through the result, but this is not what the OP wanted. – Bartosz X Oct 19 '20 at 11:51
  • 1
    I agree on the dynamic SQL as an option, that can be generated in a set based manner. Was thinking about that myself when I was going to tackle this one, but I bet it can be done even without it. I wish I had more time, I knew a recursive CTE was the way to go per my comment on the post, just haven't had the time to sit down and try to tackle this. – J.D. Oct 19 '20 at 12:52
0

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 ?

-1

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.

1
  • I see what you've done but then how do go from that to 'you can see how those totals fit in your user's budget'? – Clement Oct 13 '20 at 6:55
-2

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

1
  • The linked you shared talks about quite a different problem. Our 'bins' are not of identical size, nor do we have an infinite number of them. – Clement Oct 13 '20 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.