1

我有一个有趣的问题。我想知道一些解决这个问题的好方法。

我有一家小商店，里面有“n”个产品，每个产品都non zero price与之关联

一个产品看起来像这样

 { 
   productId:productA;  
   productName:ABC;    
   price:20$ 
}

为了提高客户保留率，我想引入组合模式进行销售。也就是说，我定义m number of combos

每个组合看起来像这样

   {    
      comboId:1;        
      comboName:2;       
      constituentProducts: {Product1, Product2};        
      comboPrice: 10$
    }

每个组合都告诉如果客户购买productA和productB，则应用组合定义中给出的折扣价格，而不是单个价格的算术总和productA一个productB 产品可能会在两个以上的组合中被提及。least price计算购物篮的最佳方法是什么

4

2 回答 2

1

如何计算最优惠的价格

看起来这种算法将运行不止一次。所以我可以随意使用一个简单的预计算步骤（对不起，如果不是这样）。

计算最优惠的价格，就是计算组合比可以应用的组。所以我只打印可以应用的组合。

工作数据类型

用 sml 表示法定义这些类型 

type index =  (productId, tag) Hashtbl.t
and  tag = {
   combos : combo list  [default is empty list]
   subIndex : index     [default is empty hash]
}
and  combo = {
   comboId : int;   
   comboName : string     
   constituentProducts : list product;
   comboPrice : int
}
and product = { 
   productId : int;
   productName : string,   
   price : int (*In fact as I understand the problem this price don't change any thing. *) 
}

预计算

预计算步骤是索引构建。

按 productsId 对组合中的所有产品进行排序。重要

let insertIntoIndex(Index index, Combo combo, int level = 0) ->
    assert level < combo.constituentProducts.length;
    tag entry = index[combo.constituentProducts[level].productId];
    if entry is null/notFound then { entry = new tag(); }
    if level + 1 == combo.constituentProducts.length
    then
    {
      entry.combos.add combo;
    }
    else
    {
      if null/notFound = entry.subIndex.get(combo.constituentProducts[level])
      then entry.subIndex.add (combo.constituentProducts[level].productId) (new tag());

      insertIntoIndex(entry.subIndex, combo, level+1)
    }

在所有组合上迭代 insertIntoIndex，以获得相同的索引。

如您所见，此索引是一种树形式。每个节点都可以计算一个组合并成为更大组合的一部分。

计算

将所有篮子产品放入一个数组中（如果需要可以重复）；

按 productId 以与排序组合相同的顺序对该数组进行排序。重要

for(int position = 0; position < array.length ; position++)
  scan(index, product, position);

let scan(index,product, position) ->
  entry = index.get array[position];
  if entry != null/notfound 
  then 
  {
    iter print entry.combos; (* or build a set of result *)

    foreach(product key : entry.subIndex.keys)
    {
      positionOfFoundKey = array.find(from = position, to = length-1 , look = key )
      if (positionOfFoundKey != -1) (* -1 for not found / null is the find function *)
    scan(entry.subIndex[key], array[positionOfFoundKey], positionOfFoundKey)
    }
  }

当产品被分类时，不会有两次组合计数，除非组合确实存在。您可以通过添加袋子找到匹配的产品来改进扫描功能，从袋子中取出已扫描的产品。

搜索的复杂性：

n x scan

扫描的复杂性：

size of bucket x maximum size of combo x number of combo

我相信这只是一个永远不应该附加的上限。

我不知道它是否是最好的，但对我来说它看起来很快，因为我不知道你的输入是什么样的。

于 2013-07-11T16:58:44.420 回答
0

有一个 HashMap，其键是组合中的产品数量，其值是另一个 HashMap < Alphabetally Sorted List of Products, Combo >。

HashMap<Integer, HashMap<List<Products>, Combo>> comboMap;

现在按字母顺序对购物车中的产品进行排序，并跟踪当前看到的最低价格以及与该价格相关的组合列表：

float lowestCurrentPrice;
List<Combo> minComboList;

有一个递归函数，从组合中可能的最大产品数量或列表大小开始，并尝试在购物车中找到具有该数量产品的组合。

如果找到，请删除组合中的产品，跟踪组合的成本，并将其添加到递归函数的结果中，该函数现在使用较小的列表重复。

如果您已经找到具有该数量产品的组合，请比较两个价格并在您的 HashMap 中保留较便宜的组合列表。

这样做直到你用完那个数字的组合。然后你减少你在一个组合中寻找的项目的数量。如果这个数字是一，那么你只需将列表中的所有项目相加，否则重复使用这个数字。

在第一次函数调用结束时，您应该在此减量结束时得到正确答案！

于 2013-07-18T17:37:26.567 回答