我有一个有趣的问题。我想知道一些解决这个问题的好方法。
我有一家小商店，里面有“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 的最佳方法是什么？购物篮
如何计算最优价格
看起来这个算法会运行不止一次。
所以我可以随意使用一个简单的预计算步骤(如果不是这样的话，我很抱歉)。
计算最佳价格，就是计算应用程序可以组合的组合。
所以我只打印可以应用的组合。
工作数据类型
定义这些类型
以 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. *)
}
预计算
预计算步骤是建立索引。
按产品 ID 对组合中的所有产品进行排序。 至关重要
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)
}
iter 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
我相信这只是一个永远不应该追加的上限。
我不知道它是否是最好的，但它对我来说看起来很快，因为我不知道你的输入是什么样的。