組合檢測機制

在一個銷售點系統中，收銀員鍵入產品類型和數量。假設有一個組合商業規則，例如購買2條可樂和2條可樂，並獲得1美元的折扣。我想創建一個機制，在購買的產品列表中自動檢測組合，然後應用適當的折扣。組合檢測機制

產品大師包含大約4000個項目。將會有大約100個連擊。交易中購買的平均產品數爲2.迄今爲止，有史以來記錄的交易中產品的最高數量爲128.

我的想法是如果交易中有3種產品（A，B，C）我必須檢查（A，B），（A，C），（B，C），（A，B，C）組合的存在。當交易具有更多產品類型時，需要檢查的組合數量會非常快。

這可能嗎？有人曾經嘗試過這樣的事情嗎？分享一些關於如何實現這一點的見解？

平臺是vb.net 2010和SQL Server 2005

編輯

一個組合將包含2至4個項目。

來源

2011-08-23 Endy Tjahjono

什麼是最小。和組合中最大數量的項目？是1到128嗎？ –

@Ajeet組合將包含2到4個項目。 –

是否所有的連擊都提供相同的節省，或者比其他連擊更好？你舉了2個薯條和2個可樂的例子= 1美元的折扣。是否有可能組合1個三明治加1個油炸加1焦炭= 1.5折優惠？算法是否應該自動提供最好的結果？如果是這樣，那麼這聽起來像貪婪算法的工作應用於揹包問題。 – oosterwal

你可以像你已經在你的文章中那樣對可能的組合進行排序，然後創建一個樹結構。如果您必須檢查一個組合，首先查找第一個項目（例如A），然後按照樹，然後檢查下一個項目（例如C）。如果你能找到這個，可能有組合，否則不可以。

不同的解決方案：將所有按您的問題排序的組合保存在散列圖中，然後查看這些組合。我可以想象這很快，但它需要大量的空間和一些時間來生成哈希映射。

來源

2011-08-23 13:16:53 Zento

此解決方案不會處理與組合中的項目相關聯的變量「數量」。 2-焦炭與4-焦炭不同。 –

你可以從剩下的物品中刪除找到的物品，然後你會再次找到2可樂組合。但是你是對的，如果你有很多項目並且想要找到儘可能多的組合，它就不起作用。 – Zento

// I figured it is easy to post code than explaining long-winded style. All are programmer here anyways 
typedef pair<string,int> item_quant; 
bool funccomp (const item_quant& lhs, const item_quant& rhs) 
{ 
    if((lhs.first < rhs.first) || (lhs.second < rhs.second)) 
     return true; 
    return false; 
} 
struct classcomp { 
    bool operator() (const vector<item_quant>& lhs, const vector<item_quant>& rhs) const 
    { 
     if(lhs.size() < rhs.size()) 
      return true; 
     for(unsigned int i=0; i< lhs.size();++i) 
     { 
      if(!funccomp(lhs[i],rhs[i])) 
       return false; 
     } 
     return true; 
    } 
} classcompObj; 



int main() 
{ 
    // Insert 
    map<vector<item_quant>,int,classcomp> table; 
    vector<item_quant> v; 
    v.push_back(make_pair("coke",2)); 
    v.push_back(make_pair("fries",2)); 
    // Dont forget to sort. 
    sort(v.begin(),v.end(),funccomp) ; 
    table[v] = 1; 

    //search 
    int disc = (*table.find(v)).second; 
    cout<<" disc = "<<disc<<endl; 
    return 0; 
}

來源

2011-08-23 14:03:32

我必須先刷新我的C++理解，但感謝您的幫助。 –

好的，所以這裏是Aglo翻譯：把每個組合看作列表。列表中的元素進行排序，使列表可比較。你有這些列表的哈希映射。添加一個新的梳子。創建一個新列表並將其添加到Hash-map。要進行搜索，只需重新創建列表並在散列圖中進行搜索即可。 –

還有一件事。定製的Trie數據結構非常適合您的任務。 Item中的每個節點都是ItemName + Number。 –

組合檢測機制

回答

相關問題