Solving the knapsack problem in PostgreSQL®の翻訳です。

ナップザック問題：休暇に最も必要と思われるアイテムをすべて収めるには？世界最高のOSデータベースの使い方をご覧ください。

PostgreSQL®でナップザック問題を解く

デベロッパーセンターを検索

休暇前の数日はわくわくします。どこかに休暇を計画し、旅に出るのが待ち遠しいことでしょう。

パンツは何枚持っていくべきか？ランニングシューズは必要か？ドライヤーは？ジャケットはどれにしよう？スーツケースのサイズを制約条件とし、最高のホリデー体験を究極のゴールとして、たくさんの決断を迫られる。

このブログ記事の目的は、テクノロジーを使って荷造りの問題を解決することだ。具体的には、PostgreSQL®と再帰的な共通テーブル式だ。

組み合わせ最適化 - ナップザック問題

この最適化のジレンマは新しいものではない。ナップザック問題という名前さえある。ナップザック問題は、重量（この例では荷物の占めるスペース）と価値**（休暇中のアイテムの利点）が定義されたアイテムのセットがあり、総重量が制限される（荷物の大きさ）という様々なユースケースに適用できます。

最終的なゴールは、重量の制約内に収まり、可能な限り最大の価値を持つアイテムのセットを考え出すことです。

例えば、次のような項目があるとしよう：

| ソックス｜10｜3
| 🎩 帽子 | 15 | 5

| 靴 | 8 | 10
| Tシャツ | 7 | 10 |

そして、私たちは20の容量を持つナップザックを持っている。

つまり、荷造りができる：

ズボン(重さ15)＋帽子(重さ5)で、合計(5+15)=20。

または

Tシャツ（重さ10）＋帽子（重さ5）＋靴下（重さ3）で合計（7＋15＋10）＝32

表の設定に基づくと、2番目の選択肢の方が総合的な値としてはるかに優れている。

(この時点で、この概念と解決策は単純化されすぎた数学的問題として提示されていることに注意する必要があります。もしあなたが靴やズボンを履かずに休暇に出かけることになったとしても、Aivenは責任を負いません！)

PostgreSQLの救出

どうすれば最良の選択ができるのか？技術が手助けしてくれるのでしょうか？もちろんだ！信頼できるPostgreSQLを引っ張り出せばいいのです（これは常に忘れずに梱包しておくべきです）。

まずはAivenのコマンドラインインターフェイスを使ってインスタンスを作成しましょう。

avn service create demo-pg  \
 --サービスタイプ pg
 --cloud google-europe-west3  \
 --plan hobbyist`Copy to clipboard

上記は、リージョン google-europe-west3 に hobbyist プランで demo-pg という PostgreSQL インスタンス (--service-type pg) を作成します。インスタンスのサイズや移動は自由です。すべての利用可能な組み合わせを確認してください。

インスタンスが起動したら（avn service wait demo-pgで待つことができる）、プロンプトからデータベースにログインする：

avn service cli demo-pg`クリップボードにコピーする

これでPostgreSQLに入った！これで新しい inventory テーブルを作成し、データセットを格納することができます。

テーブル inventory (item_id serial, item_name varchar, value int, weight int) を作成する；
insert into inventory(item_name, value, weight) values ('Socks', 10,3)；
insert into inventory(item_name, value, weight) values ('Hat', 15,5)；
insert into inventory(item_name, value, weight) values ('Trousers', 5,15)；
insert into inventory(item_name, value, weight) values ('Shoes', 8,10)；
insert into inventory(item_name, value, weight) values ('T-Shirt', 7,10);`Copy to clipboard

データを確認してみよう：

クリップボードにコピーする。

そして、期待通りの出力が得られる：

 item_id | item_name | value | weight
---------+-----------+-------+--------
 1｜ソックス｜10｜3
 2｜ 帽子｜15｜5
 3｜ズボン｜5｜15
 4｜靴｜8｜10
 5｜Tシャツ｜7｜10
(5行)``クリップボードへコピー

これで荷物のナップザック問題を解く準備ができた。

反復的アプローチとPostgreSQLの再帰的CTE

ナップザック問題を解く方法は複数あります。その1つは、試行錯誤のケースで行うことをPostgreSQLで再現することです。1つの項目を選び、それを荷物に追加し、また別の項目を選んで追加し、スーツケースが満杯になるまで繰り返します。これ以上荷物が入らなくなったら、入れた荷物の値をすべて合計し、そのリストを記録する。そして、荷物を空にして、また一からやり直し、同じアイテムの順番にならないようにする。

すべての可能なアイテムの組み合わせがチェックされたら、最大値のものを選ぶことができる。これは長く、ミスを犯しやすいプロセスだが、幸運なことにコンピューターがそれを処理してくれる。

上記のプロセスは、すべての組み合わせを見つけるために必要なステップを定義している：

1.インベントリからランダムなアイテムを1つ選ぶ。 2.アイテムを picked_itemsリストに追加し、アイテムコストを保存する。 3.別のアイテムをinventory` から選択する：

a. そのアイテムが picked_items リストに入っていないこと。

b. 現在のアイテムの weight と picked_items リストにあるすべてのアイテムの total_weight を足した値が、最大許容重量以下である。
4.新しいアイテムを picked_items リストに追加する。
5.項目 weight を total_weight に追加する。
6.インベントリ`に a と b の条件を満たす新しいアイテムが含まれるまで、ステップ#3 に戻る。

ここには、inventoryテーブルに対する逐次クエリの反復パターンが見て取れる。これをPostgreSQLにマップするにはどうすればよいでしょうか。私たちは inventory テーブルに対して、可変回数の繰り返しで select 文を実行したいと思います（picked_items のリストは異なるサイズを持つことができます）。SELECT文を再帰的に呼び出す方法が必要です。PostgreSQL recursive CTEが輝きます。

例えば、inventoryテーブルのSocksで始まる3つのアイテムの組み合わせをすべて取得することができます：

WITH RECURSIVE items(picked_items, nr_items) as (
 SELECT ARRAY[item_name] as picked_items、
 1 nr_items
 from inventory
 ここで item_name = 'Socks'
 UNION ALL
 select picked_items || item_name、
 nr_items + 1
 from inventory cross join items
 ここで nr_items+1 <= 3
)
select ˶* from items where nr_items=3;`Copy to clipboard

RECURSIVEキーワードがシーンを設定する。2つ目の SELECTステートメントでinventoryテーブルとまだ定義中のRECURSIVE itemsクエリの結果を結合します。その結果、inventoryテーブルにあるSocks` から始まる3つのアイテムの25の組み合わせがリストアップされます。

 名前 | nr_items
-----------------------------+----------
 {ソックス,ソックス,ソックス｝| 3
 {靴下、靴下、帽子｝| 3
 靴下、靴下、ズボン} {靴下、靴下、ズボン} 3| 3
 {靴下,ソックス,靴}｜3| 3
 {靴下、ソックス、Tシャツ}｜3| 3
 {靴下,帽子,靴下}｜3| 3
 ...
 {靴下,Tシャツ,帽子}｜3 ...| 3
 {靴下,Tシャツ,ズボン} ...| 3
 靴下,Tシャツ,靴} {靴下,Tシャツ,靴} 3| 3
 靴下,Tシャツ,ズボン} {靴下,Tシャツ,ズボン} 3| 3
(25行)`クリップボードへコピー

ナップザック制約を追加する

上記のクエリは、3つのアイテムに限定されたinventoryテーブルで利用可能なすべての組み合わせを返します。しかし、我々のナップザック問題には異なる制約があります：

一度選んだアイテムを再利用することはできません。
シーケンスの長さは固定ではなく、total_costによって決まります。

では、上記の制約を再帰クエリにどのように追加できるかを確認してみましょう：

WITH RECURSIVE items(item_id, picked_items, nr_items, total_weight, total_value) as (
 SELECT
 item_id、
 ARRAY[item_name] as picked_items、
 1 nr_items、
 weight total_weight、
 値 total_value
 在庫から
 UNION ALL
 select
 inventory.item_id、
 picked_items || item_name、
 nr_items + 1、
 weight + total_weight、
 値 + total_value
 from inventory cross join items
 where
 ARRAY[item_name] = false
 かつ weight + total_weight <= 20
 かつ inventory.item_id > items.item_id
)
select ˶* from items order by total_value;`Copy to clipboard

クエリを分割してみましょう。最初の部分は再帰クエリの種で、inventoryテーブルからすべての行を選択します。

SELECT
 item_id、
 ARRAY[item_name] as picked_items、
 1 nr_items、
 weight total_weight、
 値 total_value
from inventory`Copy to clipboard

item_idを単一の値として保存し、それをpicked_items 配列に追加する。また、アイテムの総数 (1)、関連する weightをtotal_weight として、valueをtotal_value として格納する。UNION ALL の次のフェーズは再帰的な処理である：

選択
 inventory.item_id、
 picked_items || item_name、
 nr_items + 1、
 weight + total_weight、
 value + total_value
from inventory cross join items
where
 ARRAY[item_name] = false
 かつ weight + total_weight <= 20
 and inventory.item_id > items.item_id`クリップボードにコピー

item_idを選択し、1つの値として格納し、配列picked_itemsに追加する。アイテムのカウントに+1を加算し、現在のアイテムのweightとvalueをそれぞれ前に選択したアイテムのtotal_weightとtotal_value` に加算する。

面白いのは次のセクションである。我々は inventory と items (再帰クエリ) の間で CROSS JOIN を実行し、テーブルのデカルト積を作成する。言い換えると、inventoryに存在する各アイテムの行とitemsに存在する各行が掛け合わされる。あまり賢くはないが、フィルタリングが魔法をかけている：

picked_items::varchar[] @> ARRAY[item_name] = false: item_name が既に picked_items のリストに含まれている行を結果セットから除外する。
weight + total_weight <= 20: 事前に計算した total_weight と関連する weight の合計が、荷物のために設定した 20 のしきい値を超えるすべてのアイテムを結果セットから除外する。
inventory.item_id > items.item_id: 最適化フィルタです。{ズボン,靴} と {靴,ズボン} は同じアイテムの2つの組み合わせであり、1つだけを残したいのです。このように、アイテムの選択を item_id の昇順でのみ許可することで、同じアイテムのサブセットを何度も分析することがなくなり、パフォーマンスを向上させることができる。

上記のクエリの結果は以下のようになります：

 item_id | picked_items | nr_items | total_weight | total_value
---------+---------------------------+----------+--------------+-------------
 3 | {ズボン｝| 1 | 15 | 5
 5｜｛Tシャツ｝| 1 | 10 | 7
 4｜{ 靴｝| 1 | 10 | 8
 1｜{ソックス}｜1｜3｜10｜8| 1 | 3 | 10
 2｜{帽子}｜1｜5｜15| 1 | 5 | 15
 5｜{ 靴,Tシャツ}｜ 2｜ 20｜ 15| 2 | 20 | 15
 3｜{ 靴下,ズボン}｜ 2｜ 18｜ 15| 2 | 18 | 15
 5｜{ 靴下,Tシャツ}｜ 2｜ 13｜ 17| 2 | 13 | 17
 4｜{ ソックス,シューズ}｜2｜13｜18｜17| 2 | 13 | 18
 3｜ 帽子,ズボン| 2 | 20 | 20
 5｜{ 帽子,Tシャツ}｜2｜15｜22| 2 | 15 | 22
 4｜ 帽子,靴| 2 | 15 | 23
 2｜{ 靴下,帽子｝| 2 | 8 | 25
 5｜{ ソックス,帽子,Tシャツ}｜3｜18｜32| 3 | 18 | 32
 4｜{ 靴下,帽子,靴}｜3｜18｜33| 3 | 18 | 33
(15行)``クリップボードへコピー

容量20の荷物に入るアイテムのすべての組み合わせが表示される。total_valueで並べ替えると、{靴下,帽子,靴}の組み合わせが最大値であることがわかる。

繰り返しますが、これは純粋な理論的練習であって、休日のパッキングを提案するものではありません。他にも追加すべき制約がありますか？これを基本として、実際のケースで必要となる複雑さを自由に追加してください！

いくつかの考え

ナップザック問題は非常に一般的なものです。プロジェクトの計画からリソースの割り当てまで、ある種の限られたバケツに可能な限り多くの項目を収める必要がある様々な実際のケースがあります。PostgreSQLの再帰CTEは、問い合わせの反復的なアプローチが必要な場合に有効な選択肢となります。

ここで注意しなければならないのは、再帰がフィルタによって適切に制限されていないと、性能がすぐに暴走してしまうということです。再帰を定義し、境界を設定し、PostgreSQLが休暇前の荷造りにどのように役立つかを楽しんでください！

参考文献はこちらです：

ナップザック問題の定義と変形
Aiven for PostgreSQL 計画と雲情報
PostgreSQL recursive CTEのドキュメントです。
AivenブログのPostgreSQL入門

まとめ

Aivenのサービスをまだご利用でない方は今すぐAiven無料トライアル登録にご登録ください！

また、changelogやRSS feeds、LinkedInやTwitterのアカウントをフォローして、製品や機能関連の最新情報をご確認ください。