SQL - Group records by N dollar amount

Question

My question is somewhat similar to

however I want to group by a maximum dollar amount

So I have 20 records with a total amount of 50,000, I need to break them into groups so that each group has a maximum amount of 10,000.

I tried using a running value, giving the records a rank and them summing the values <= the current rank, then breaking them into SubGroups using Floor((RunningValue - amount) / 10000), but there are circumstances where it goes over the 10,000 maximum

Sample data, you can see here that SubGroup 1 is over 10,000

SubGroupNo  RowNo   amount  RunningValue
0           1       790.5   790.5
0           2       790.5   1581
0           3       790.5   2371.5
0           4       790.5   3162
0           5       744     3906
0           6       744     4650
0           7       1348.5  5998.5
0           8       1348.5  7347
0           9       1348.5  8695.5
1           10      1348.5  10044
1           11      1302    11346
1           12      1302    12648
1           13      1302    13950
1           14      1302    15252
1           15      1255.5  16507.5
1           16      1209    17716.5
1           17      1116    18832.5
1           18      1116    19948.5
2           19      1302    21250.5
2           20      1302    22552.5
2           21      1302    23854.5
2           22      1255.5  25110
2           23      1255.5  26365.5
2           24      976.5   27342

That's the [knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem), best solved outside SQL — Andomar, Aug 14 '12 at 17:54
Somewhat, except the records must stay in their `RowNo` order — msmucker0527, Aug 14 '12 at 17:57

Kermit · Accepted Answer · 2012-08-15T17:06:00.493

This is probably not the best approach, but it works. It assumes that your RowNo's are sequential. If not, I would add ROW_NUMBER() with this solution.

Iteration-based approach

SQL Fiddle

DECLARE @runningTotal decimal(7,2), @sgn tinyint, @cursor int, @count int
SET @runningTotal = '0.00'
SET @sgn = 0
SET @cursor = 1
SELECT @count = COUNT(*) FROM tbl

WHILE @cursor <= @count
BEGIN
    SELECT @runningTotal = @runningTotal + amount FROM tbl WHERE RowNo = @cursor
    IF @runningTotal > 10000
        BEGIN
            SELECT @runningTotal = amount FROM dbo.tbl WHERE RowNo = @cursor
            SET @sgn = @sgn + 1
        END
    UPDATE tbl SET SubGroupNo = @sgn WHERE RowNo = @cursor
    SET @cursor = @cursor + 1
END

Edit 1: Cursor-based approach

SET NOCOUNT ON;

DECLARE @SubGroupNo tinyint, @RowNo smallint, 
    @amount decimal(8,2), @RunningTotal decimal(7,2)

SET @SubGroupNo = 0
SET @RunningTotal = '0.00'

DECLARE row_cursor CURSOR FOR
    SELECT RowNo, amount FROM dbo.tbl

OPEN row_cursor

FETCH NEXT FROM row_cursor
INTO @RowNo, @amount

WHILE @@FETCH_STATUS = 0
BEGIN
    SET @RunningTotal = @RunningTotal + @amount

    IF @RunningTotal > 10000
        BEGIN
            SET @RunningTotal = @amount
            SET @SubGroupNo = @SubGroupNo + 1
        END
    PRINT @RowNo 
    PRINT @RunningTotal
    PRINT @SubGroupNo

    UPDATE dbo.tbl SET SubGroupNo = @SubGroupNo WHERE RowNo = @RowNo

    FETCH NEXT FROM row_cursor
    INTO @RowNo, @amount
END

CLOSE row_cursor
DEALLOCATE row_cursor

Result

| SUBGROUPNO | ROWNO | AMOUNT | RUNNINGVALUE |
----------------------------------------------
|          0 |     1 |  790.5 |        790.5 |
|          0 |     2 |  790.5 |         1581 |
|          0 |     3 |  790.5 |       2371.5 |
|          0 |     4 |  790.5 |         3162 |
|          0 |     5 |    744 |         3906 |
|          0 |     6 |    744 |         4650 |
|          0 |     7 | 1348.5 |       5998.5 |
|          0 |     8 | 1348.5 |         7347 |
|          0 |     9 | 1348.5 |       8695.5 |
|          1 |    10 | 1348.5 |        10044 |
|          1 |    11 |   1302 |        11346 |
|          1 |    12 |   1302 |        12648 |
|          1 |    13 |   1302 |        13950 |
|          1 |    14 |   1302 |        15252 |
|          1 |    15 | 1255.5 |      16507.5 |
|          1 |    16 |   1209 |      17716.5 |
|          2 |    17 |   1116 |      18832.5 |
|          2 |    18 |   1116 |      19948.5 |
|          2 |    19 |   1302 |      21250.5 |
|          2 |    20 |   1302 |      22552.5 |
|          2 |    21 |   1302 |      23854.5 |
|          2 |    22 | 1255.5 |        25110 |
|          2 |    23 | 1255.5 |      26365.5 |
|          2 |    24 |  976.5 |        27342 |

Schema

CREATE TABLE tbl (
  SubGroupNo tinyint,
  RowNo tinyint PRIMARY KEY,
  amount decimal(6,2),
  RunningValue decimal(7,2))

INSERT INTO tbl (RowNo, amount, RunningValue)
VALUES
(1, '790.5', '790.5'),
(2, '790.5', '1581'),
(3, '790.5', '2371.5'),
(4, '790.5', '3162'),
(5, '744', '3906'),
(6, '744', '4650'),
(7, '1348.5', '5998.5'),
(8, '1348.5', '7347'),
(9, '1348.5', '8695.5'),
(10, '1348.5', '10044'),
(11, '1302', '11346'),
(12, '1302', '12648'),
(13, '1302', '13950'),
(14, '1302', '15252'),
(15, '1255.5', '16507.5'),
(16, '1209', '17716.5'),
(17, '1116', '18832.5'),
(18, '1116', '19948.5'),
(19, '1302', '21250.5'),
(20, '1302', '22552.5'),
(21, '1302', '23854.5'),
(22, '1255.5', '25110'),
(23, '1255.5', '26365.5'),
(24, '976.5', '27342')

This is pretty close to the way I did it other than minor differences (WHILE instead of CURSOR). I was hoping to find a cleaner approach without looping through each record, but this may be the only way — msmucker0527, Aug 14 '12 at 19:32
@msmucker0527 I think a CURSOR approach may be cleaner. Sorry I couldn't be of more assistance. — Kermit, Aug 14 '12 at 19:40

SQL - Group records by N dollar amount

1 Answers1

Iteration-based approach

Edit 1: Cursor-based approach