1

I have a interesting problem. I would like to know some good approaches to solve this.

I have a small store in which I have 'n' number of products Each product as a non zero price associated with it

A product looks like this

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

To enhance the customer retention, I would like to bring in combo model to sell. That is, I define m number of combos

Each combo looks like this

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

Each combo tells that if a customer buys productA and productB, then apply a discounted price given in the combo definition rather than the arithmetic sum of individual price of productA and productB A product may be mentioned in more than two combos. What is the best way to calculate the least price for a shopping basket

Nandish A
  • 1,645
  • 5
  • 26
  • 41
  • Does comboPrice should be use like this totalPrice = a.price + b.price - abCombo.comboPrice ? – Galigator Jul 11 '13 at 13:34
  • Is it allow to do an heavy pre-computation of index before running the algorithm for one basket ? – Galigator Jul 11 '13 at 15:32
  • Can a combo have more than two items? If not then it might be beneficial to consider this as a graph problem with n vertices and m edges. The cost of vertex being either it's cost if the vertex is used or half of the used edge cost. It may also be useful to think in terms of cost reduction. I suspect this is probably exponential time in the worst case. – Nuclearman Jul 13 '13 at 08:40
  • Yes a combo can have any number of products. I would say a purchase of `pepsi`, `sandwich` and `chips` is `comboSnacks` – Nandish A Jul 16 '13 at 06:30

2 Answers2

1

How to calculate the best price

It look like this algorithms will be run more than one time. So I feel free to use an eavy pre-compute step (sorry if it is not the case).

Computing the best price, is computing the group of combos than can by apply. So I'm only printing combos that can be apply.

working data types

define thoses type in sml notation 

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. *) 
}

pre-compute

The precompute step is index building.

Sort all products in your combos by the productsId. vital

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 over all your combos, for the same index.

As you can see this index is a form of tree. Each node can math a combo and be a part of a greater combo.

computation

Put all the basket products into an array (with repetition if need);

Sort that array by productId in the same order as use for sorting combos. vital

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)
    }
  }

as product are sorted, there will be no combos counts twice, unless the combos is really present. You can improve the scan function by adding a bag to found the matching product, remove from the bag the product that have been scan.

Complexity of the search :

n x scan

Complexity of scan :

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

I believe this is just an upper bound that should never append.

I don't know if it is the best, but it look fast enouph to me as I don't know what your inputs look like.

Galigator
  • 8,957
  • 2
  • 25
  • 39
0

Have a HashMap whose key is the number of products in a combo and whose value is another HashMap < Alphabetically Sorted List of Products, Combo >.

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

Now alphabetically sort the products in the shopping cart and keep track of the lowest price seen currently and the List of Combos that is associated with that price:

float lowestCurrentPrice;
List<Combo> minComboList;

Have a recursive function that starts with either the highest possible number of products in a combo or the size of the list, and try to find a combo in the shopping cart with that number of products.

If found, remove the products in the combo, keep track of the cost of combo, and add this to the result of your recursive function that now repeats using the smaller list.

If you had already found a combo with that number of products, compare the two prices and keep the list of combos that was less expensive in your HashMap.

Do this until you run out of combos of that number. Then you decrement the number of items you are looking for in a combo. If this number is one then you just sum up all the items in the list, otherwise repeat using this number.

You should have the correct answer by the end of this decrement at the end of your first function call!

Eric Kim
  • 41
  • 5