1

編集：

皆さんに読んでもらうと、私が注目されなくなると言われています。謝罪いたします。より簡単なバージョンは次のとおりです。

ビルは店から 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 つ持つ方法は (おそらく GROUP BY を使用して) ありますか?

ありがとう！

a

4

4 に答える 4

2

合計するとちょうど 30 ドルになるすべてのサブセットを求めています。

これは、部分和の問題やナップザックの問題によく似ているため、単純なクエリでこれを実行できるとは思えません。おそらく T-SQL に頼らなければならないでしょうが、それでもおそらく見苦しくなるでしょう。

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

于 2008-12-29T09:48:46.537 に答える
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 の同等物については不明です。

于 2008-12-29T10:37:55.283 に答える
0

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

かなり良い推測ができる既存のアルゴリズムのいくつかを使用できますが、それらはすべてSQL以外のものであると思います。

私はあなたの問題の近似をすることを提案します：

希望する価格に最適な記事を1つ見つけるプロシージャ/クエリを作成し、それをもう一度呼び出して新しい変更を加えます。完璧ではありませんが、仕事をします。

于 2008-12-29T11:31:31.150 に答える
0

group by ではできないと思います。

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

30 ドルを超えるアイテムがある場合は、それらを省略できます。

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

于 2008-12-29T09:40:01.627 に答える