组合检测机制

在一个销售点系统中，收银员键入产品类型和数量。假设有一个组合商业规则，例如购买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。 –

组合检测机制

回答

相关问题