T-SQL Dynamic Combinatorics / Backpack Approach

Question

I think my question is related to a variant of the problem with the backpack, but I can not find a solution for this:

Say you are in a store and must buy 21 screws. They only offer them in bags:

• Bag X - 16 Screws - $ 1.56 per screw - $ 25 Total
• Bag Y - 8 screws - $ 2.25 per screw - $ 18 Total
• Bag Z - 4 Screws - $ 1.75 per screw - $ 7 Total

Now you need to figure out which bags you should buy to get 21 screws (or more!) At the lowest price.

So, I have a table with all the bags and a variable to determine the required amount. As a result, I need a table with a name and the required amount.

Unfortunately sqlfiddle does not work. But at least here are some sample data:

declare @bags table (id int, qty int, price decimal(19,4)) insert into @bags values (10, 16, 25.00) ,(20, 8, 18.00) ,(30, 4, 7.00) declare @ReqQty int = 21 

I really appreciate your help! I hope we can solve this problem, since I need to configure our ERP system of our company with this important function.

Thank you in advance!

Edit: I read the entire wikipedia article about a backpack and it says: Overflow approximation algorithm. Perhaps an approximation algorithm will be generated where we can overfill the allowable weight limit a bit. You would like to achieve at least as high a total cost as this B binding, but you are allowed to exceed the weight limit ... Currently, the solution is unknown for this approximation algorithm.

So it seems I should use a greedy algorithm instead of reinventing the wheel ?;)

Answer 1

Here is a possible solution. I will see if I can finish this tomorrow, since it is now almost 3 am. The basic logic is. It remains only to trace using the prev_w values. Just bounce back (starting at line best_price ) until you reach line w=0 . The differences between the w current and previous row give the size of the bag that you must buy at every step.

In your example, the solution route, obviously, is:
"w = 24, w = 8, w = 4, w = 0", which means "buy bags: 16, 4, 4.".
These 3 bags cost $ 39.

This decision assumes that the person is not going to buy
more than 1000 screws (that's what @limit is).

Script draft:

 -- use TEST; declare @limit decimal(19,4); set @limit = 1000; create table #bags ( id int primary key, qty int, price decimal(19,4), unit_price decimal(19,4), w int, -- weight v decimal(19,4) -- value ); insert into #bags(id, qty, price) values (10, 16, 25.00) ,(20, 8, 18.00) ,(30, 4, 7.00); declare @ReqQty int; set @ReqQty = 21; update #bags set unit_price = price / ( 1.0 * qty ); update #bags set w = qty; update #bags set v = -price; select * From #bags; create table #m(w int primary key, m int, prev_w int); declare @w int; set @w = 0; while (@w< =@limit ) begin insert into #m(w) values (@w); set @w = @w + 1; end; update #m set m = 0; set @w = 1; declare @x decimal(19,4); declare @y decimal(19,4); update m1 set m1.m = 0 from #m m1 where m1.w = 0; while (@w< =@limit ) begin select @x = max(bv + m2.m) from #m m1 join #bags b on m1.w >= bw and m1.w = @w join #m m2 on m2.w = m1.wb.w; select @y = min(m22.w) from #m m11 join #bags bb on m11.w >= bb.w and m11.w = @w join #m m22 on m22.w = m11.w-bb.w where (bb.v + m22.m) = ( @x ); update m1 set m1.m = @x, m1.prev_w = @y from #m m1 where m1.w = @w; set @w = @w + 1; end; select * from #m; select -m1.m as best_price from #m m1 where m1.w = (select min(m2.w) from #m m2 where m2.w >= @ReqQty and (m2.m is not null)); drop table #bags; drop table #m; 

Script final version:

 -- use TEST; declare @limit decimal(19,4); set @limit = 1000; declare @ReqQty int; set @ReqQty = 21; create table #bags ( id int primary key, qty int, price decimal(19,4), unit_price decimal(19,4), w int, -- weight v decimal(19,4), -- value reqAmount int, CONSTRAINT UNQ_qty UNIQUE(qty) ); insert into #bags(id, qty, price) values (10, 16, 25.00) ,(20, 7, 14.00) ,(30, 4, 7.00); update #bags set unit_price = price / ( 1.0 * qty ); update #bags set w = qty; update #bags set v = -price; update #bags set reqAmount = 0; -- Uncomment the next line when debugging! -- select * From #bags; create table #m(w int primary key, m int, prev_w int); declare @w int; set @w = 0; while (@w< =@limit ) begin insert into #m(w) values (@w); set @w = @w + 1; end; update #m set m = 0; set @w = 1; declare @x decimal(19,4); declare @y decimal(19,4); update m1 set m1.m = 0 from #m m1 where m1.w = 0; while (@w< =@limit ) begin select @x = max(bv + m2.m) from #m m1 join #bags b on m1.w >= bw and m1.w = @w join #m m2 on m2.w = m1.wb.w; select @y = min(m22.w) from #m m11 join #bags bb on m11.w >= bb.w and m11.w = @w join #m m22 on m22.w = m11.w-bb.w where (bb.v + m22.m) = ( @x ); update m1 set m1.m = @x, m1.prev_w = @y from #m m1 where m1.w = @w; set @w = @w + 1; end; -- Uncomment the next line when debugging! -- select * from #m; declare @z int; set @z = -1; select @x = -m1.m, @y = m1.w , @z = m1.prev_w from #m m1 where m1.w = -- The next line contained a bug. It fixed now. -- (select min(m2.w) from #m m2 where m2.w >= @ReqQty and (m2.m is not null)); ( select top 1 best.w from ( select m1.m, max(m1.w) as w from #m m1 where m1.m is not null group by m1.m ) best where best.w >= @ReqQty and best.w < 2 * @ReqQty order by best.m desc ) -- Uncomment the next line when debugging! -- select * From #m m1 where m1.w = @y; while (@y > 0) begin update #bags set reqAmount = reqAmount + 1 where qty = @ y-@z ; select @x = -m1.m, @y = m1.w , @z = m1.prev_w from #m m1 where m1.w = @z; end; select * from #bags; select sum(price * reqAmount) as best_price from #bags; drop table #bags; drop table #m; 

Answer 2

I decided to come up with a slightly different approach. This set is installed, and the general idea is to find all possible combinations of amounts that meet the desired condition, and then choose the cheapest one.

Steps:

• taking into account @ReqQty , for each type of bag, find how many of these amounts it makes sense to include in the expression (that is, if the bag contains 5 pieces, and we want to purchase 12 pieces, it makes sense to consider 1, 2 or 3 bags, but 4 bags obviously too much).
• find all possible combination of all the sums and their sums (i.e. for the type Bag A with the sums 1, 2 and 3 and the type Bag B with the sums 1 and 2 you can try: A * 1 + B * 1 , A * 2 + B * 1 , A * 3 + B * 1 , A * 1 + B * 2 , A * 2 + B * 2 , A * 3 + B * 2 )
• calculate all combinations (this is actually done on the fly), that is, find the total quantity and total price.
• Get the row with the lowest price that is higher or equal to the required value.

This is the whole solution with the provided OP data examples:

(the decision has been changed, a new version is available below!)

 -- sample data declare @ReqQty int = 21 declare @Bags table (Code nvarchar(1), Quantity int, Price decimal(10,2)) insert into @Bags select 'X', 16, 25.00 union select 'Y', 8, 18.00 union select 'Z', 4, 7 ; with -- helper table: all possible integer numbers <= @ReqQty Nums (I) as ( select 1 union all select I + 1 from Nums where I < @ReqQty ), -- possible amounts of each kind bag that make sense -- ie with 3-piece bag and 5-piece requirement it -- is worth checking 1 (x3 = 3) or 2 (x2 = 6) bags, but -- 3, 4... would be definitely too much Vars (Code, Amount) as ( select B.Code, Nums.I from @Bags as B inner join Nums on B.Quantity * I - @ReqQty < B.Quantity ), Sums (Expr, Amount, TotalQuantity, TotalPrice) as ( -- take each kind of bag with every amount as recursion root select convert(nvarchar(100), V.Code + '(' + convert(nvarchar(100), Amount) + ')'), Amount, B.Quantity * Amount, convert(decimal(10, 2), B.Price * Amount) from Vars as V inner join @Bags as B on V.Code = B.Code union all -- add different kind of bag to the summary -- 'Sums.Amount >= V.Amount' is to eliminate at least some duplicates select convert(nvarchar(100), Expr + ' + ' + V.Code + '(' + convert(nvarchar(100), V.Amount) + ')'), V.Amount, Sums.TotalQuantity + B.Quantity * V.Amount, convert(decimal(10, 2), Sums.TotalPrice + B.Price * V.Amount) from Vars as V inner join @Bags as B on V.Code = B.Code inner join Sums on (charindex(V.Code, Expr) = 0) and Sums.Amount >= V.Amount ) -- now find lowest price that matches required quantity -- remove 'top 1' to see all combinations select top 1 Expr, TotalQuantity, TotalPrice from Sums where TotalQuantity >= @ReqQty order by TotalPrice asc 

For the data of this sample, this is the result:

 Expr TotalQuantity TotalPrice Z(2) + X(1) 24 39.00 

The solution is definitely not perfect:

• I do not like to use charindex to eliminate the same packages.
• all duplicate combinations should be removed.
• I'm not sure about the effectiveness

but I just didn’t have enough time or skills to come up with smarter ideas. I think it's nice that this is a purely announcement-based solution.

EDIT

I changed the solution a bit to get rid of charindex (and thus get rid of text-based packet identifier dependencies). Unfortunately, I had to add a sum of 0 for each kind of bag that made even more combinations, but didn't seem to have a noticeable effect on performance. Also at the same price a combination with a large number of items is shown. :-)

 -- sample data declare @ReqQty int = 21 declare @Bags table (Code nvarchar(1), Quantity int, Price decimal(10,2)) insert into @Bags select 'X', 16, 25.00 union select 'Y', 8, 18.00 union select 'Z', 4, 7.00 ; with -- helper table to apply order to bag types Bags (Code, Quantity, Price, BI) as ( select Code, Quantity, Price, ROW_NUMBER() over (order by Code) from @Bags ), -- helper table: all possible integer numbers <= @ReqQty Nums (I) as ( select 0 union all select I + 1 from Nums where I < @ReqQty ), -- possible amounts of each kind bag that make sense -- ie with 3-piece bag and 5-piece requirement it -- is worth checking 1 (x3 = 3) or 2 (x2 = 6) bags, but -- 3, 4... would be definitely too much Vars (Code, Amount) as ( select B.Code, Nums.I from Bags as B inner join Nums on B.Quantity * I - @ReqQty < B.Quantity ), Sums (Expr, Amount, BI, TotalQuantity, TotalPrice) as ( -- take first kind of bag with every amount as recursion root select convert(nvarchar(100), V.Code + '(' + convert(nvarchar(100), Amount) + ')'), Amount, B.BI, B.Quantity * Amount, convert(decimal(10, 2), B.Price * Amount) from Vars as V inner join Bags as B on V.Code = B.Code where B.BI = 1 union all -- add different kind of bag to the summary select convert(nvarchar(100), Expr + ' + ' + V.Code + '(' + convert(nvarchar(100), V.Amount) + ')'), V.Amount, B.BI, Sums.TotalQuantity + B.Quantity * V.Amount, convert(decimal(10, 2), Sums.TotalPrice + B.Price * V.Amount) from Vars as V inner join Bags as B on V.Code = B.Code -- take next bag kind according to order inner join Sums on B.BI = Sums.BI + 1 and Sums.TotalQuantity + B.Quantity * V.Amount - @ReqQty < B.Quantity ) -- now find lowest price that matches required quantity -- remove 'top 1' to see all combinations select top 1 Expr, TotalQuantity, TotalPrice from Sums where TotalQuantity >= @ReqQty order by TotalPrice asc, TotalQuantity desc, Expr asc