How to use SQL to implement logic similar to making change?

Question

The table Item has a field NUM_UNITS.

id      num_units
--      ---------
1       2
2       4
3       1
4       7

For the above rowset, sum(num_units) = (2 + 4 + 1 + 7) = 14.

I would like to write SQL code that allows me to change 14 to 14 - N (i.e. decrease), N being any number.

N = 3: row1: num_units=0, row3: num_units=0.

N = 4: row2: num_units=0

N = 5: row2: num_units=0, row3: num_units=0

N = 6: row2: num_units=0, row1: num_units=0, row3: num_units=0

N = 7: row2: num_units=0, row1: num_units=0, row3: num_units=0, row4: num_units=6

The goal is to effect the update such that SUM(NUM_UNITS) descreases by N rows.

Here's what I came up with so far: I made a function that tests the distance to the desired result when choosing N1 of the largest rows and N2 of the smallest rows.

ALTER FUNCTION F
(
    @GOAL INT,
    @P1 INT,
    @P2 INT
)
RETURNS INT
AS
BEGIN
    DECLARE @X INT = (
        SELECT SUM(NUM_UNITS)
        FROM (
            SELECT TOP(@P1) ID, NUM_UNITS
            FROM ITEM
            ORDER BY NUM_UNITS DESC
            UNION
            SELECT TOP(@P2) ID, NUM_UNITS
            FROM ITEM
            ORDER BY NUM_UNITS ASC
        ) J
    )
    RETURN @GOAL - @X
END
GO

Now the trick is to call this successively, as well as find the next smallest row to remove the remainder from.

All that said, I'm interested in solving the problem, not in doing it this way in particular. The logic reminds me of writing a program to make change. I.e. if something costs X and the cashier receives Y, how does s/he go about choosing the bills and coins to give back optimally?

Any thoughts appreciated. Suggestions on feasability and/or direction to go in are appreciated. I could do this in another programming language but I'm trying to see if I can do it in SQL, partially as a learning experience.

Answer 1

Let N = 14

Here are the full contents of Table1 before the algorithm runs.

Here are the full contents of Table1 after the algorithm runs.

This code is designed to run in one query window / SP.

Declarations:

declare @N int = 14
declare @Remaining int = @N
declare @CurrentID int
declare @Current_Num_Units int

Step 1: Remove as many large records as possible

Declare MaxCursor CURSOR FAST_FORWARD FOR
select id, num_units from Table1 order by num_units desc, id

-- Step 1: Remove as many large records as possible
OPEN MaxCursor
FETCH NEXT FROM MaxCursor
INTO @CurrentID, @Current_Num_Units

WHILE @@FETCH_STATUS = 0
BEGIN

    if @Current_Num_Units <= @Remaining
    begin
        set @Remaining = @Remaining - @Current_Num_Units -- eliminate row and subtract from @Remaining
        update Table1 set num_units = 0 where ID = @CurrentID
    end
    else
    begin
        break -- exit loop if the this "next" record is too large to subtract from
    end

    -- grab the next record
    FETCH NEXT FROM MaxCursor
    INTO @CurrentID, @Current_Num_Units
END 

CLOSE MaxCursor
DEALLOCATE MaxCursor

Step 2: Remove as many small records as possible

-- Step2: Eliminate as many small records as possible
Declare MinCursor CURSOR FAST_FORWARD FOR
select id, num_units from Table1 where num_Units > 0 order by num_units, id  -- ascending instead of descending, j

Open MinCursor
FETCH NEXT FROM MinCursor
INTO @CurrentID, @Current_Num_Units

WHILE @@FETCH_STATUS = 0
BEGIN

    if @Current_Num_Units <= @Remaining
    begin
        set @Remaining = @Remaining - @Current_Num_Units -- eliminate row and subtract from @Remaining
        update Table1 set num_units = 0 where ID = @CurrentID
    end
    else
    begin
        break -- exit loop if the this "next" record is too large to subtract from
    end

    -- grab the next record
    FETCH NEXT FROM MinCursor
    INTO @CurrentID, @Current_Num_Units
End

CLOSE MinCursor
DEALLOCATE MinCursor

Step 3: Reduce the next available smallest record by the remainder

-- Step 3. Take the next record and subtract the remaining difference from its num_units
set @CurrentID = (select top 1 ID from Table1 where num_units > 0 order by num_units, id)

update Table1 set num_units = num_units - @Remaining where ID = @CurrentID

-- Now we have reduced by N, starting with the high records, then the min records, then we took the difference out of a remaining record.
select * from table1

Notes

• This is not good SQL Code. SQL is best suited for set-based operations -- almost none of this is occurring. For a large dataset, you're almost certainly better suited doing this in a standard language like C# or VB.NET and saving the changes to the DB after.
• The looping above is handled with Cursors. Most of the time when somebody thinks they need a cursor to do something in SQL, they are doing something that is better suited to a standard coding environment as mentioned above.
• A few assumptions were made, such as some records always existing in the table, etc. I just wanted to lay down a framework that you can build off of.