sql - 総重量を見つけるための SQL クエリ

Question

列「ボックス番号」と「重量」を持つテーブルに 30 のレコードがあります。30 個の箱のうち、重量の合計が 1000 kg に最も近い 20 個の箱を見つけなければなりません。

Answer 1

ナップサック問題について読むことをお勧めします

Answer 2

SQLサーバー：

select TOP 20 box_number 
from t_boxes 
group by box_number 
order by ABS(SUM(box_weight) - 1000) ASC

編集：私があなたの質問を誤解していて、実際にナップザックの問題を解決したい場合。これは SQL で実際に行うべきことですが、非常に適切な名前でこの記事を読むことができます: SQL Server の完全に不適切な使用について.

Answer 3

SQL でこれを解決する方法は推奨されておらず、どのマシンでも実行できない可能性があります。ただし、ブルート フォース ソリューションは次のように表現できます。

select box1.id, box2.id, . . . ,
       (box1.weight + box2.weight + . . .)
from box box1 join
     box box2
     on box2.id > box1.id join
     box box3
     on box3.id > box2.id join
     box box4
     on box4.id > box3.id
     . . .
     box box20
     on box20.id > box19.id
order by abs(1000 - (box1.weight + box2.weight + . . .))

「オン」条件により、ボックスの各セットが一意の ID 順に並べられて 1 回表示されることが保証されます。「左結合」ではなく「結合」を使用すると、正確に 20 個のボックスが得られます。