Essentially solving a linear equation in sql

Question

I hope someone can help.

Essentially I have a table which contains fixed size data bundles such as: 50gb, 100gb, 250gb and 1000gb. There are more bundles than this but this is to show examples.

Essentially I want to create something where I pass it a number such as 1250gb and it will give me a list of which bundle sizes make up this 1250gb bundle from the table mentioned above.

How would I go about doing something like this?

Answer 1

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

1. Set target size @targetGB = 1550 to have an example with repeated bundles
   and excluding bundles that are too big.
2. Define an initial value @sumGB = 0 to increment as we go.
3. Select the biggest bundle @sumPartGB that we can add to @sumGB
   and stay within the @targetGB size limit.
4. Store that part of the sum in a result table @result.
5. Increment @sumGB with the selected bundle.
6. 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.