CODEWITHSUNDEEP
mysqlsql
N. Phan
N. Phan

Reputation: 13

Selecting rows if the total sum of a row is equal to X

I have a table that holds items and their "weight" and it looks like this:

items
-----

id          weight
----------  ----------
1           1
2           5
3           2
4           9
5           8
6           4
7           1
8           2

What I'm trying to get is a group where the sum(weight) is exactly X, while honouring the order in which were inserted.

For example, if I were looking for X = 3, this should return:

id          weight
----------  ----------
1           1
3           2

Even though the sum of ids 7 and 8 is 3 as well.

Or if I were looking for X = 7 should return

id          weight
----------  ----------
2           5
3           2

Although the sum of the ids 1, 3 and 6 also sums 7.

I'm kind of lost in this problem and haven't been able to come up with a query that does at least something similar, but thinking this problem through, it might get extremely complex for the RDBMS to handle. Could this be done with a query? if not, what's the best way I can query the database to get the minimum amount of data to work with?

Edit: As Twelfth says, I need to return the sum, regardless of the amount of rows it returns, so if I were to ask for X = 20, I should get:

id          weight
----------  ----------
1           1
3           2
4           9
5           8

Upvotes: 1

Views: 81

Answers (1)

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

This could turn out to be very difficult in sql. What you're attempting to do is solve the knapsack problem, which is non-trivial.

The knapsack problem is interesting from the perspective of computer science for many reasons:

  • The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no possible algorithm both correct and fast (polynomial-time) on all cases, unless P=NP.
  • While the decision problem is NP-complete, the optimization problem is NP-hard, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger, thus solving the decision problem NP-complete).
  • There is a pseudo-polynomial time algorithm using dynamic programming.
  • There is a fully polynomial-time approximation scheme, which uses the pseudo-polynomial time algorithm as a subroutine, described below.
  • Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly.

Upvotes: 1

Related Questions