mysqlサブトータルの検索

Question

編集：

皆さんに読んでもらうことは、私があまり注意を払うことを意味すると言われています。謝罪いたします。これがより簡単なバージョンです：

ビルは、店から100ドル相当のアイテムを獲得しました。

彼は、ちょうど30ドルを取り戻すのに十分なアイテムを返したいと思っています。

ストアには、彼がこれを行うのに役立つリターンシステムがあります。

彼がアイテムをスキャンした後のデータは次のとおりです。

       item ¦   price ¦

socks             4.00
cheap tv         22.00
book on tape      9.00
book on paper     7.00
party hats        3.00
picture frame    10.00
hammer            5.00
juicer           16.00
mysql guide      24.00

total items  ¦ total price ¦
            9   100.00

Option 1
===============
item ¦          price ¦
cheap tv        22.00
party hats       3.00
hammer           5.00
===============

Option 2
===============
item ¦          price ¦

socks            4.00
picture frame   10.00
juicer          16.00
===============

Option 3
===============
item ¦          price ¦

book on tape    9.00
hammer          5.00
juicer         16.00

私はこれをすべて作り上げたので、おそらくいくつかの選択肢を逃したでしょう。

だから、大きな問題は次のとおりです。

（おそらくグループでは）アイテムの組み合わせを常に返すクエリを1つ持っている方法はありますか？

ありがとう！

a

Answer 1

アイテムの数が十分に小さい場合は、SQLでこれを強制的に強制的に強制することができます。これはすぐに解決策を書くかもしれませんが、おそらくより賢いことをしたいと思うでしょう。 」のように聞こえますナップサックの問題「これはNP完全です。

アイテムの数が多い場合は、動的プログラミングアルゴリズムを掘り下げる必要があります。これがアプリケーションにとってどれほど重要かを自問する必要があります。

アイテムの数が比較的少ない場合、これをブルートフォースすることができる場合があります。一致する1,2または3つのアイテムの組み合わせを見つけるブルートフォースSQLステートメント（これが求められたもの）は次のとおりです。これが満足のいくものでない場合、SQLはこのジョブに適したツールではないかもしれません。

SELECT
   i1.id AS id1,
   NULL AS id2,
   NULL AS id3,
   i1.amount
FROM
   items i1
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount AS total
FROM
   items i1,
   items i2
WHERE
   i1.amount + i2.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount + i3.amount AS total
FROM
   items i1,
   items i2,
   items i3
WHERE
   i1.amount + i2.amount + i3.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id AND
   i2.id <> i3.id

Oracleでは、Cube関数を使用してこれを一般的なバージョンに変換しますが、MySQLの同等物についてはわかりません。

Answer 2

正確に30ドルまで合計されているすべてのサブセットを求めています。

これはよく似ています サブセット合計問題, 、 と ナップサックの問題, 、だから私はあなたが簡単なクエリでこれを行うことができると強く疑っています。おそらくT-SQLに頼らなければならないでしょうが、それでも醜いように見えるでしょう。

プログラミングはここに行く方法だと思います。

Answer 3

私はそれができるとは思わない。

選択したプログラミング言語またはストアドプロシージャのいずれかで、すべての順列を見つける/試すよりも良い方法を考えることはできません。

30ドル以上のアイテムがあれば、それらを省略できます。

いくつかの基準で「最良の」オプションが必要な場合、いくつかの改善があります。

Answer 4

この問題は、実際にはp/npです。たとえば、ブルートフォース検索なしでは、おそらく最適な記事の価格を見つけることができません。クライアントのストアが大きい場合は、非常に長く続く検索を見つけることができます。

かなり良い推測を与えることができる既存のアルゴリズムの一部を使用できますが、それらはすべて非SQLのアルゴリズムであることを恐れています。

私はあなたの問題の近似を行うことをお勧めします：

必要な価格に最適な1つの記事を見つけるプロシージャ/クエリを作成し、新しい変更のために再びそれを呼び出すよりも。完璧ではありませんが、仕事をします。