Return items that add up to a maximum given value from a table

Question

I'm trying to build a sql query that will return a list of IDs that have a total sum, which is less than OR greater than a given value using the least number of items.

Here's an example of the table I'll be querying.

ID    Value 
-----------  
226   2.3   
331   3.1   
25    1.5   
28    1.5   
29    1.2   
52    5.2   
38    3.5   

Here it is sorted by Value asc.

ID   Value
----------  
29   1.2  
25   1.5  
28   1.5  
226  2.3  
331  3.1  
38   3.5  
52   5.2  

Example A :

If my value is 6, I would expect the query to return IDs 29, 25, 28 and 226. 1.2 + 1.5 + 1.5 + 2.3 = 6.5

Example B :

If my value is 19, I would expect the query to return all of the IDs (29, 25, 28, 226, 331, 38, 52).
1.2 + 1.5 + 1.5 + 2.3 + 3.1 + 3.5 + 5.2 = 18.3

I've tried the suggested answer found here: SQL select elements where sum of field is less than N

However, that's not giving me exactly what I need since it only returns IDs that add up to LESS than the set value. Also it is assuming that the ID is ascending which isn't the case when I sort by asc value.

Is this even possible within a sql statement? or would I have to do a procedure/function to accomplish this task?

Answer 1

Assuming you are talking the values in ascending order and you want to stop when you are closest to the desired total then:

SQL Fiddle

Oracle 11g R2 Schema Setup:

CREATE TABLE data ( ID, Value ) AS
          SELECT 226, 2.3 FROM DUAL
UNION ALL SELECT 331, 3.1 FROM DUAL
UNION ALL SELECT 25, 1.5 FROM DUAL
UNION ALL SELECT 28, 1.5 FROM DUAL
UNION ALL SELECT 29, 1.2 FROM DUAL
UNION ALL SELECT 52, 5.2 FROM DUAL
UNION ALL SELECT 38, 3.5 FROM DUAL;

Query 1:

WITH differences AS (
  SELECT ID,
         Value, 
         ABS(
           SUM( Value ) OVER ( ORDER BY Value ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW )
           - 6 -- REPLACE THIS WITH :desired_total
         ) AS difference
 FROM    data
),
min_difference AS (
  SELECT MIN( Value ) KEEP ( DENSE_RANK FIRST ORDER BY difference ASC ) AS max_value,
         MIN( ID ) KEEP ( DENSE_RANK FIRST ORDER BY difference ASC ) AS max_id
  FROM differences
)
SELECT ID,
       Value
FROM   differences d
       INNER JOIN
       min_difference m
       ON (  d.value < max_value
          OR ( d.value = m.max_value AND d.id <= max_id ) )

Results:

|  ID | VALUE |
|-----|-------|
| 226 |   2.3 |
|  25 |   1.5 |
|  28 |   1.5 |
|  29 |   1.2 |

Edit - Stops when running total is just greater than or equal to desired total

SQL Fiddle

Query 1:

Calculate the running totals for each row (in order of ascending value) then select all the rows where the running total is less than the desired total and also the next row (with the minimum running total of the totals greater than or equal to the desired total).

WITH running_totals AS (
  SELECT ID,
         Value,
         SUM( Value ) OVER ( ORDER BY Value ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS running_total
 FROM    data
)
SELECT ID,
       Value
FROM   running_totals
WHERE  running_total < 6
UNION ALL
SELECT MIN( id    ) KEEP ( DENSE_RANK FIRST ORDER BY running_total ),
       MIN( value ) KEEP ( DENSE_RANK FIRST ORDER BY running_total )
FROM   running_totals
WHERE  running_total >= 6

Results:

|  ID | VALUE |
|-----|-------|
|  29 |   1.2 |
|  28 |   1.5 |
|  25 |   1.5 |
| 226 |   2.3 |

EDIT 2 - An alternative method:

WITH running_totals AS (
  SELECT ID,
         Value,
         SUM( Value ) OVER ( ORDER BY Value, ID ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS running_total,
         ROW_NUMBER() OVER ( ORDER BY Value, ID ) AS idx
  FROM   data
)
SELECT ID,
       Value
FROM   running_totals
WHERE  idx <= (SELECT MAX(idx) + 1 FROM running_totals WHERE running_total < 6 );