how to find Sum(field) in condition ie "select * from table where sum(field) < 150"

Question

I have to retrieve only particular records whose sum value of size field is <=150. I have table like below ...

userid size
1       70
2      100   
3       50
4       25
5      120
6       90

The output should be ...

userid size
1       70
3       50
4       25

For example, if we add 70,50,25 we get 145 which is <=150.

How would I write a query to accomplish this?

Answer 1

What you're looking for is a greedy algorithm. You can't really do this with one SQL statement.

Answer 2

It's similar to the subset sum problem. You are definitely going to be into exponential time ...

There are several ways to solve subset sum in time exponential in N. The most naïve algorithm would be to cycle through all subsets of N numbers and, for every one of them, check if the subset sums to the right number. The running time is of order O(2^N*N), since there are 2N subsets and, to check each subset, we need to sum at most N elements.

Unless you can constrain the problem to smaller subsets.

Answer 3

According to your definition as it stands you could get any of these tables:

userid size    userid size
1       70     2      100   

userid size    userid size
3       50     4       25

userid size    userid size
5      120     6       90

userid size    userid size
1       70     2      100   
3       50     3       50

userid size    userid size
1       70     2      100   
4       25     4       25

userid size    userid size
1       70     4       25
3       50     6       90
4       25

userid size    userid size
4       25     3       50
5      120     6       90

SQL sucks at guessing. Do you mean to say you want the most users who's total size is under a certain limit? You'll need to create a temp table of all the combinations of users, then select the ones who's total size is less then the limit, then select the one with the most users, and possibly the lowest user ID or something. Either way, it won't be fast due to the first step.

Answer 4

Here's a query which will produce the above results:

SELECT * FROM `users` u
WHERE (select sum(size) from `users` where size <= u.size order by size) < 150
ORDER BY userid

However, the problem you describe of wanting the selection of users which would most closely fit into a given size, is a bin packing problem. This is an NP-Hard problem, and won't be easily solved with ANSI SQL. However, the above seems to return the right result, but in fact it simply starts with the smallest item, and continues to add items until the bin is full.

A general, more effective bin packing algorithm would is to start with the largest item and continue to add smaller ones as they fit. This algorithm would select users 5 and 4.

Answer 5

But do you want to maximize the number of results or minimize or you simply don't care? first two cases is constraints optimization for which there should be solution using SQL, the latter (as mentioned above) requires greedy strategy.