So finden Sie die Summe (Feld) in der Bedingung "Wählen * aus der Tabelle, wo Summe (Feld) <150"

Question

Ich muss nur bestimmte Datensätze abrufen, deren Summenwert der Größe Feld ist < = 150. Ich habe folgende Tabelle wie ...

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

Die Ausgabe sollte ...

userid size 
1  70 
3  50 
4  25 

Zum Beispiel, wenn wir 70,50,25 fügen wir 145 erhalten, die < = 150 ist.

Wie würde ich eine Abfrage schreiben, um dies zu erreichen?

Answer 1

Hier ist eine Abfrage, die die obigen Ergebnisse produzieren:

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

jedoch das Problem, das Sie zu wollen, die Auswahl der Benutzer beschreiben, die am ehesten in einer bestimmten Größe passen würde, ist ein bin packing problem. Dies ist ein NP-Hard Problem und wird nicht einfach mit ANSI SQL gelöst werden. Das obige Ergebnis scheint jedoch das richtige Ergebnis zu liefern, aber tatsächlich beginnt es einfach mit dem kleinsten Element und fügt weitere Elemente hinzu, bis das Fach voll ist.

Ein allgemeinerer, effektiverer Bin-Packing-Algorithmus wäre, mit dem größten Element zu beginnen und weiterhin kleinere hinzuzufügen, wenn sie passen. Dieser Algorithmus würde Benutzer 5 und 4 auswählen.

Answer 2

Was Sie suchen, ist ein greedy algorithm. Sie können dies wirklich nicht mit einer SQL-Anweisung tun.

Answer 3

Es ist ähnlich wie die . Sie werden auf jeden Fall in exponentielle Zeit sein ...

Es gibt mehr Möglichkeiten Teilmenge Summe in der Zeit exponentiell in N. Der naive Algorithmus wäre Zyklus durch alle Teilmengen von N Zahlen zu lösen und , für jede von ihnen, überprüfen Sie, ob die Teilmenge auf die richtige Zahl summiert. Die Laufzeit ist von der Reihenfolge O (2^N * N), da 2N Teilmengen sind und, um jede Teilmenge zu überprüfen, müssen wir höchstens N Elemente summieren.

Es sei denn, Sie können das Problem auf kleinere Teilmengen beschränken.

Answer 4

Nach Ihrer Definition, wie es steht Ihnen eine dieser Tabellen erhalten könnte:

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 saugt bei erraten. Willst du damit sagen, dass du die meisten Nutzer willst, deren Gesamtgröße unter einem bestimmten Limit liegt? Sie müssen eine temporäre Tabelle aller Kombinationen von Benutzern erstellen und dann diejenigen auswählen, deren Gesamtgröße kleiner als das Limit ist. Wählen Sie dann diejenige mit den meisten Benutzern und möglicherweise die niedrigste Benutzer-ID oder so. In jedem Fall wird es aufgrund des ersten Schrittes nicht schnell sein.

Answer 5

Aber möchten Sie die Anzahl der Ergebnisse maximieren oder zu minimieren, oder Sie einfach nicht interessiert? Die ersten beiden Fälle sind Constraints-Optimierungen, für die es eine Lösung mit SQL geben sollte, wobei letztere (wie oben erwähnt) gierige Strategie erfordert.