Dynamic T-SQL approach for combinatorics/knapsack

Question

I guess my question has to do with a variant of the knapsack problem, but I can't really come up with a solution for this:

Let's say you are in a hardware store and need to 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 have to figure out which Bags you should buy to get your 21 screws (or more!) for the lowest possible price.

So what I got is a table with all the bags and a variable to define the required amount. What I need as a result should be a table with the bagname and the required amount.

Unfortunately sqlfiddle is down.. But at least here's the example 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! Hope we can get this solved, as I need to customize our companys ERP System with this important function.

Thank you in advance!

Edit: I read the whole wikipedia article about knapsack and there it says: Overfill approximation algorithm It may be possible to generate an approximation algorithm where we can slightly overflow the allowed weight limit. You would want to achieve at least as high a total value as the given bound B, but you're allowed to exceed the weight limit... Currently the solution is unknown for this approximation algorithm.

So it seems I better use a greedy algorithm instead of inventig the wheel? ;)

Answer 1

Here is a possible solution. I will see if I can finish it tomorrow as it's almost 3 AM here now. The main logic is there. All that's left to be done is to trace back using the prev_w values. Just jump back (starting from the best_price row) till you reach the w=0 row. The differences between the ws of current and the previous row give you the size of the bag you have to buy at each step.

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

This solution assumes the person is not going to buy
more than 1000 screws (this is what @limit is there for).

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(b.v + m2.m) 
    from
    #m m1 
    join #bags b on m1.w >= b.w and m1.w = @w
    join #m m2 on m2.w = m1.w-b.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(b.v + m2.m) 
    from
    #m m1 
    join #bags b on m1.w >= b.w and m1.w = @w
    join #m m2 on m2.w = m1.w-b.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's 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've decided to come up with a slightly different approach. This one is set based and the general idea is to find all possible combinations of amounts of bags that match the required condition, then select the cheapest one.

Steps:

• given @ReqQty, for each kind of Bag find how many of such Bag does it make sense to include in expression (thats is if bag contains 5 pieces, and we want to purchase 12 pieces, it makes sense to consider 1, 2 or 3 bags, but 4 bags would be obviously too much)
• find all possible combination of all Bags and their amounts (that is i.e. for Bag kind A with amounts 1, 2 and 3, and Bag kind B with amounts 1 and 2 one 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 actually done on the fly), that is find total quantity and total price
• get row with lowest price that is higher or equal to required quantity

This is whole solution with sample data OP provided:

(The solution was modified, 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
-- i.e. 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 a given sample data this is the result:

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

The solution is definitely not perfect:

• I do not like using charindex to eliminate same types of bags
• all duplicate combinations should be eliminated
• I am not sure about efficiency

but I simply lacked time or skills to come up with more clever ideas. What I think is nice is that it's purely set-based, declarative solution.

EDIT

I've modified the solution a bit to get rid of charindex (and thus get rid of dependency of text based bag identifiers). Unfortunately I had to add 0 amount for each kind of bag which made even more combinations but it seems to have no noticeable impact on performance. Also for the same price the combination with more pieces 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
-- i.e. 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