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 

我可能錯過了幾個選項，因爲我做了這一切了。

所以，最大的問題是：

有沒有一種方法（與GRO​​UP BY，可能）有一個查詢將返回項目有史以來可能的組合？

謝謝！

a

Answer 1

如果項目數量足夠小，可以用SQL強制執行此操作。這可能會很快寫出解決方案，但您可能想要做更聰明的事情。聽起來像NP完整的「knapsack problem」。

如果項目數量很大，則需要深入研究動態編程算法。你必須問自己這對你的應用程序有多重要。

如果項目的數量相對較少，您可能可以對此進行暴力破解。一個蠻力SQL語句（這就是你所要求的）查找1,2或3個匹配項目的組合如下。如果這不能令人滿意，那麼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美元，您可以省略它們。

如果你想通過某些標準獲得「最佳」選項，會有一些改進。

Answer 3

你要求的所有子集總計正好30美元。

這聽起來很像subset sum problem和knapsack problem，所以我強烈懷疑你可以用簡單的查詢來做到這一點。你可能不得不轉向T-SQL，但即使這樣也可能看起來很醜。

我認爲編程是去這裏的路。

Answer 4

這個問題實際上是P/NP。例如，如果沒有蠻力搜索，你可能找不到最合適的文章價格，而且如果你的客戶商店很大 - 你會發現搜索很長時間。

你可以使用一些現有的算法，可以給你不錯的猜測，但我怕，他們都是非SQL的。

我會建議做你的問題的近似：

CREATE PROCEDURE /查詢發現一篇文章最適合想要的價格，而且比再次調用它新的變化，你有。不完美，但會完成這項工作。