There is a restriction to this subset sum problem, namely that we are looking for the minimal required bundles. This allows us to start looking from the biggest to the smallest bundle under the target size (just like handing back cash change, you start from the largest note and work your way down to the smallest coin).
Sample data
Added an extra bundle with size 2000
for demonstration purposes.
create table bundles
(
sizeGB int
);
insert into bundles (sizeGB) values
(50),
(100),
(250),
(1000),
(2000);
Solution
- Set target size
@targetGB = 1550
to have an example with repeated bundles
and excluding bundles that are too big.
- Define an initial value
@sumGB = 0
to increment as we go.
- Select the biggest bundle
@sumPartGB
that we can add to @sumGB
and stay within the @targetGB
size limit.
- Store that part of the sum in a result table
@result
.
- Increment
@sumGB
with the selected bundle.
- Repeat as long as
@sumGB < @targetGB
.
In code:
declare @targetGB int = 1550;
declare @sumGB int = 0;
declare @result table
(
sizeGB int
);
while @sumGB < @targetGB
begin
declare @sumPartGB int;
select top 1 @sumPartGB = b.sizeGB
from bundles b
where b.sizeGB + @sumGB <= @targetGB
order by b.sizeGB desc;
insert into @result (sizeGB) values (@sumPartGB);
set @sumGB += @sumPartGB;
end
select r.sizeGB as sumParts
from @result r
order by r.sizeGB desc;
Result
sumParts
--------
1000
250
250
50
Calling this algorithm could be done through a table-valued function (= function that returns a table). How you store or wrap this algorithm ultimately depends on your application.
Define function
create function getBundles(@targetGB int)
returns @result table (sizeGB int)
as
begin
declare @sumGB int = 0;
while @sumGB < @targetGB
begin
declare @sumPartGB int;
select top 1 @sumPartGB = b.sizeGB
from bundles b
where b.sizeGB + @sumGB <= @targetGB
order by b.sizeGB desc;
insert into @result (sizeGB) values (@sumPartGB);
set @sumGB += @sumPartGB;
end
return;
end;
Call function
select r.sizeGB as sumParts
from getBundles(1550) r
order by r.sizeGB desc;
Fiddle to see everything in action.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…