retrieve rows until their quantity sum is less then @quantity

I have table: data(id, name, quantity)

I would like to write a stored procedure that will get @quantity and retrieve me the minimum rows that their quantity sum is bigger or equal to @quantity.

Example:

id    name    quantity
1     a       3
2     b       1
3     c       7
4     d       2

For @quantity=5 good res开发者_StackOverflow社区ults can be:

1, a, 3
2, b, 1
3, c, 7

OR

1, a, 3
4, d, 2

OR

3, c, 7

and so on. the sum of quantity in the rsults must be greater or equal to @quantity but I dont need extra rows.

EDITED: explanation added

declare @goal int
set @goal = 5
;with numbered as
(
  -- this first query gives a sequential number to all records
  -- the biggest quantities are number 1,2,3 etc to the smallest quantities
  -- this ordering is because the minimum number of rows is most quickly
  -- achieved by combining the biggest quantities
  select id, name, quantity,
    row_number() over (order by quantity desc) rn
  from data
), cte as
( 
  -- this is a common table expression
  -- it starts off with the record with the biggest quantity
  select id, name, quantity, rn, sumsofar = quantity
  from numbered
  where rn = 1

  union all

  -- this is the recursive part
  -- "CTE" references the previous record in the loop
  select b.*, sumsofar + b.quantity
  from numbered b
  inner join cte a on b.rn = a.rn+1  -- add the next record (as ordered)
  -- continue the loop only if the goal is not yet reached
  where a.sumsofar < @goal
)
-- this finally selects all the records that have been collected to satisfy the @goal
select * from cte

-- NOTE: if @goal cannot be reached even with all records added up, this just
--       returns all records

This only works for SQL Server 2005+, due to using Common Table Expressions.

This should work better than the below, but the below also works in 2000 or you can compare the two in 2005/8 for what works best for you.

declare @goal int set @goal = 5

select c.*
from data c inner join 
(
    select top 1 * from
    (
        -- find the pivotal a.id on which the goal is reached
        select a.id, a.quantity, sum(b.quantity) s
        from data a
        -- this works on the b records on quantity desc, and id asc
        inner join data b
          on b.quantity < a.quantity
          or (b.quantity=a.quantity and b.id > a.id)
        group by a.id, a.quantity
        having sum(b.quantity) >= @goal
        union all
        -- if ALL records together cannot satisfy the GOAL
        -- we add a id=-1 record to mark this fact
        select -1, null, null
    ) oneonly
    -- find the min required, or return the fake -1 ID
    ORDER BY case when id=-1 then 1 else 0 end, s ASC, id ASC
) d
  on c.quantity > d.quantity
  or (c.quantity=d.quantity and c.id <= d.id)
  or d.id = -1   -- this matches all rows in C