sql - Optimal solution for interview question -

recently in job interview, given following problem.

say have following table

widget_name        |     widget_costs      | in_stock ---------------------------------------------------------                   |         15.00          |    1 b                   |         30.00          |    1 c                   |         20.00          |    1 d                   |         25.00          |    1 

where widget_name holds name of widget, widget_costs price of widget, , in stock constant of 1.

now business insurance have deductible. looking find sql statement tell me every widget , it's price exceeds deductible. if dedudctible $50.00 above return

widget_name        |     widget_costs      | in_stock ---------------------------------------------------------                   |         15.00          |    1 d                   |         25.00          |    1 

since widgets b , c used meet deductible

the closest following

select      * (      select            widget_name,            widget_price      interview.tbl_widgets      minus      select widget_name,widget_price      (           select                 widget_name,                widget_price,                 50 - sum(widget_price) on (order widget_price  rows between unbounded preceding , current row) running_total           interview.tbl_widgets       )        running_total >= 0 ) ; 

which gives me

widget_name        |     widget_costs      | in_stock --------------------------------------------------------- c                   |         20.00          |    1 d                   |         25.00          |    1 

because uses , b meet majority of deductible

i hoping might able show me correct answer

edit: understood interview question asking this. given table of widgets , prices , given dollar amount, substract many of widgets can dollar amount , return widgets , prices remain

this looks bin packing problem these hard solve sql.

if search on bin packing + sql, you'll find how find sum(field) in condition ie “select * table sum(field) < 150” same problem except want add not in it.

i couldn't accepted answer brianegge work wrote in general interesting

..the problem describe of wanting selection of users closely fit given size, bin packing problem. np-hard problem, , won't solved ansi sql. however, above seems return right result, in fact starts smallest item, , continues add items until bin full.

a general, more effective bin packing algorithm start largest item , continue add smaller ones fit. algorithm select users 5 , 4.

so advice write cursor loop on table (it wouldn't pretty).

aaron alton gives nice link series of articles attempts solve bin packing problem sql concludes best use cursor it.