combinatorics/knapsack 的动态 T-SQL 方法
Dynamic T-SQL approach for combinatorics/knapsack
我想我的问题与背包问题的变体有关，但我真的想不出解决方案：
假设您在一家五金店，需要购买 21 个螺丝。
他们只提供袋装：
- 包 X - 16 个螺丝 - 每个螺丝 1.56 美元 - 总计 25 美元
- 包 Y - 8 个螺丝 - 每个螺丝 2.25 美元 - 总计 18 美元
- 包 Z - 4 个螺丝 - 每个螺丝 1.75 美元 - 总计 7 美元
现在您必须弄清楚应该购买哪些包才能以尽可能低的价格获得 21 个（或更多！）螺丝。
所以我得到的是一个 table，其中包含所有袋子和一个定义所需数量的变量。因此，我需要的应该是 table，其中包含行李名称和所需金额。
不幸的是，sqlfiddle 已关闭。但至少这里是示例数据：
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
非常感谢您的帮助！希望我们能解决这个问题，因为我需要用这个重要的功能定制我们公司的ERP系统。
提前致谢！
编辑：
我阅读了关于背包的整篇维基百科文章，上面写着：
溢出近似算法
可能会生成一个近似算法，我们可以稍微溢出允许的重量限制。您可能希望达到至少与给定界限 B 一样高的总值，但您可以超过重量限制......
目前此近似算法的解未知。
看来我最好使用贪心算法而不是发明轮子？ ;)
这是一个可能的解决方案。我看看明天能不能完成它，因为现在已经快凌晨 3 点了。主要逻辑在那里。剩下要做的就是使用 prev_w 值进行追溯。只需向后跳转（从 best_price 行开始），直到到达 w=0 行。当前行和上一行的 w 之间的差异为您提供了每一步必须购买的包的尺寸。
在你的例子中，解决方案显然是：
"w=24, w=8, w=4, w=0" 翻译成 "to buy bags: 16, 4, 4.".
这 3 个袋子售价 39 美元。
此解决方案假定此人不会购买
超过 1000 个螺丝（这就是 @limit 的作用）。
脚本草稿：
-- 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;
脚本最终版本：
-- 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;
我决定想出一个稍微不同的方法。这个是基于集合的，一般的想法是找到符合要求条件的袋子数量的所有可能组合，然后 select 最便宜的那个。
步骤：
- 给定
@ReqQty，对于每种包，找出有多少这样的包在表达式中包含是有意义的（也就是说，如果包包含 5 件，而我们想购买 12 件，它使考虑1、2或3袋是有意义的，但4袋显然太多了）
- 找到所有包及其数量的所有可能组合（即对于数量为 1、2 和 3 的包种类
A，以及数量为 1 和 2 的包种类 B，可以尝试：A * 1 + B * 1、A * 2 + B * 1、A * 3 + B * 1、A * 1 + B * 2、A * 2 + B * 2、A * 3 + B * 2)
- 计算所有组合（这实际上是即时完成的），即找到总数量和总价格
- 获取价格高于或等于所需数量的最低行
这是完整的解决方案，提供了示例数据 OP：
（解决方案已修改，下方有新版本！）
-- 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
对于给定的示例数据，结果如下：
Expr TotalQuantity TotalPrice
Z(2) + X(1) 24 39.00
解决方案肯定不完美：
- 我不喜欢用
charindex来消除相同类型的包
- 应消除所有重复组合
- 我不确定效率
但我只是缺乏时间或技能来想出更聪明的点子。我认为很好的是它是纯粹基于集合的声明式解决方案。
编辑
我对解决方案做了一些修改以摆脱 charindex（从而摆脱了对基于文本的包标识符的依赖）。不幸的是，我不得不为每种袋子添加 0 数量，这使得组合更多，但它似乎对性能没有明显影响。还以相同的价格显示了更多件的组合。 :-)
-- 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
我想我的问题与背包问题的变体有关，但我真的想不出解决方案：
假设您在一家五金店，需要购买 21 个螺丝。 他们只提供袋装：
- 包 X - 16 个螺丝 - 每个螺丝 1.56 美元 - 总计 25 美元
- 包 Y - 8 个螺丝 - 每个螺丝 2.25 美元 - 总计 18 美元
- 包 Z - 4 个螺丝 - 每个螺丝 1.75 美元 - 总计 7 美元
现在您必须弄清楚应该购买哪些包才能以尽可能低的价格获得 21 个（或更多！）螺丝。
所以我得到的是一个 table，其中包含所有袋子和一个定义所需数量的变量。因此，我需要的应该是 table，其中包含行李名称和所需金额。
不幸的是，sqlfiddle 已关闭。但至少这里是示例数据：
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
非常感谢您的帮助！希望我们能解决这个问题，因为我需要用这个重要的功能定制我们公司的ERP系统。
提前致谢！
编辑： 我阅读了关于背包的整篇维基百科文章，上面写着： 溢出近似算法 可能会生成一个近似算法，我们可以稍微溢出允许的重量限制。您可能希望达到至少与给定界限 B 一样高的总值，但您可以超过重量限制...... 目前此近似算法的解未知。
看来我最好使用贪心算法而不是发明轮子？ ;)
这是一个可能的解决方案。我看看明天能不能完成它，因为现在已经快凌晨 3 点了。主要逻辑在那里。剩下要做的就是使用 prev_w 值进行追溯。只需向后跳转（从 best_price 行开始），直到到达 w=0 行。当前行和上一行的 w 之间的差异为您提供了每一步必须购买的包的尺寸。
在你的例子中，解决方案显然是：
"w=24, w=8, w=4, w=0" 翻译成 "to buy bags: 16, 4, 4.".
这 3 个袋子售价 39 美元。
此解决方案假定此人不会购买
超过 1000 个螺丝（这就是 @limit 的作用）。
脚本草稿：
-- 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;
脚本最终版本：
-- 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;
我决定想出一个稍微不同的方法。这个是基于集合的，一般的想法是找到符合要求条件的袋子数量的所有可能组合，然后 select 最便宜的那个。
步骤：
- 给定
@ReqQty，对于每种包，找出有多少这样的包在表达式中包含是有意义的（也就是说，如果包包含 5 件，而我们想购买 12 件，它使考虑1、2或3袋是有意义的，但4袋显然太多了） - 找到所有包及其数量的所有可能组合（即对于数量为 1、2 和 3 的包种类
A，以及数量为 1 和 2 的包种类B，可以尝试：A * 1 + B * 1、A * 2 + B * 1、A * 3 + B * 1、A * 1 + B * 2、A * 2 + B * 2、A * 3 + B * 2) - 计算所有组合（这实际上是即时完成的），即找到总数量和总价格
- 获取价格高于或等于所需数量的最低行
这是完整的解决方案，提供了示例数据 OP：
（解决方案已修改，下方有新版本！）
-- 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
对于给定的示例数据，结果如下：
Expr TotalQuantity TotalPrice
Z(2) + X(1) 24 39.00
解决方案肯定不完美：
- 我不喜欢用
charindex来消除相同类型的包 - 应消除所有重复组合
- 我不确定效率
但我只是缺乏时间或技能来想出更聪明的点子。我认为很好的是它是纯粹基于集合的声明式解决方案。
编辑
我对解决方案做了一些修改以摆脱 charindex（从而摆脱了对基于文本的包标识符的依赖）。不幸的是，我不得不为每种袋子添加 0 数量，这使得组合更多，但它似乎对性能没有明显影响。还以相同的价格显示了更多件的组合。 :-)
-- 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