algorithm - How to calculate the best price -

this question has answer here:

• selecting combination of minimum cost 5 answers

i have interesting problem. know approaches solve this.

i have small store in have 'n' number of products each product non 0 price associated it

a product looks this

 {     productid:producta;      productname:abc;        price:20$  } 

to enhance customer retention, bring in combo model sell. is, define m number of combos

each combo looks this

   {           comboid:1;               comboname:2;              constituentproducts: {product1, product2};               comboprice: 10$     } 

each combo tells if customer buys producta , productb, apply discounted price given in combo definition rather arithmetic sum of individual price of producta , productb product may mentioned in more 2 combos. best way calculate least price shopping basket

how calculate best price

it algorithms run more 1 time. feel free use eavy pre-compute step (sorry if not case).

computing best price, computing group of combos can apply. i'm printing combos can apply.

working data types

define thoses type in sml notation

type index =  (productid, tag) hashtbl.t ,  tag = {    combos : combo list  [default empty list]    subindex : index     [default empty hash] } ,  combo = {    comboid : int;       comboname : string         constituentproducts : list product;    comboprice : int } , product = {     productid : int;    productname : string,       price : int (*in fact understand problem price don't change thing. *)  } 

pre-compute

the precompute step index building.

sort products in combos 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 null/notfound { entry = new tag(); }     if level + 1 == combo.constituentproducts.length         {       entry.combos.add combo;     }     else     {       if null/notfound = entry.subindex.get(combo.constituentproducts[level])       entry.subindex.add (combo.constituentproducts[level].productid) (new tag());        insertintoindex(entry.subindex, combo, level+1)     } 

iter insertintoindex on combos, same index.

as can see index form of tree. each node can math combo , part of greater combo.

computation

put basket products array (with repetition if need);

sort array productid in same order use 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       {     iter print entry.combos; (* or build set of result *)      foreach(product key : entry.subindex.keys)     {       positionoffoundkey = array.find(from = position, = length-1 , = key )       if (positionoffoundkey != -1) (* -1 not found / null find function *)     scan(entry.subindex[key], array[positionoffoundkey], positionoffoundkey)     }   } 

as product sorted, there no combos counts twice, unless combos present. can improve scan function adding bag found matching product, remove bag product have been scan.

complexity of search :

n x scan 

complexity of scan :

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

i believe upper bound should never append.

i don't know if best, fast enouph me don't know inputs like.