algorithm問題

twaiho2003

今日係A1 買早餐, 發覺個收銀打左好多日都打唔熟部機,
我只係買三文治加COFFEE, 佢要十幾click先搞掂

有冇一種algorithm
係預先set左一個list
A = $8
B = $8
C = $10
A+B = $10
A+C = $14

如果我買A+B, 收銀就淨係需要打A同B, 電腦GEN個total = $10出黎
如果我買A+B+C,收銀就淨係打A同B同C,  電腦自動搵最平既組合, $10 + $10 = $20

twaiho2003

諗到小小概念, 將組合數量group埋一組,   
x + x 為一組
x + x + x 為一組
每組sorting 由減最多去到減最少,
A+B = $10 (-6)
A+C = $14 (-4)
A = $8
B = $8
C = $10

如果加入新既set,     set個constraint唔準貴過散買
例如 ,
A+B已經 係-6
A+B+C 唔準貴過總和既-6, ($26 - $6),   最貴只可$20

hihihi123hk

Assume we got all Key-value Pair ( Group -> Price)

Raw Input

=> List of possible Combination

=> List of Price  

=> Min.

7h1r733n

今日係A1 買早餐, 發覺個收銀打左好多日都打唔熟部機,
我只係買三文治加COFFEE, 佢要十幾click先搞掂

有 ...
twaiho2003 發表於 2016-9-2 10:13

其實... 寫cross sale係好麻煩.. 特別係如果A+B+C都可以係一個餐的話...

清仔

黎個真係一個正既問題
我覺得重點係有幾多件product/combo
一件餐廳其實用foreach 咁去對都無問題
但好似百佳咁… 太多件貨就會好慢
所以個solution 應該係N(1) 的

snoopy11hk

黎個真係一個正既問題
我覺得重點係有幾多件product/combo
一件餐廳其實用foreach 咁去對都無問題
但好似百 ...
清仔 發表於 2016-9-4 13:19

其實係 MST (Minimum Spanning Tree)問題黎...

EITCo

當A, B, C分別要買a, b, c件
樓主問題可以化約成Shortest path problem
https://en.wikipedia.org/wiki/Shortest_path_problem
一開始未買野時在起點(A=0, B=0, C=0)，買齊到終點(a, b, c)
起點終點之間仲有(0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1)等等節點
散叫A, B, C或AB, BC等餐都係連接節點間的路

於是想簡單可以用Dijkstra's algorithm
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Algorithm仲有更深奧的變體就要慢慢硏究

清仔

其實係 MST (Minimum Spanning Tree)問題黎...
snoopy11hk 發表於 2016-9-4 01:29 PM

係呀…要用tree…

LoneGumMan

Dijkstra's ++

有個簡化版, 不過有一個問題 :)

1. orderItemList = {a, b, c, .... }
   
2. ruleList = { (a,b):10, (a,c):14, (a):8, (b):8, (c):10, .... }
   
3. // rule list sorting:
   
4. // (1) number of items, desc; (2) price, asc
   
5. // this should give customer the overall best price ... ?
   
6. price = 0
   
7. while ( orderItemList.notEmpty() ) {
   
8.     matchIdx = findFirstMatch(ruleList, orderItemList); // traverse ruleList, find the entry where all keys are in orderItemList
   
9.     rule = ruleList[matchIdx]
   
10.     price += rule.price();
    
11.     orderIList.removeAll(rule.items())
    
12.     ruleUsed.add(rule)
    
13. }

複製代碼

有機會因為價錢O既安排, (a,b) 同 (a,c) o既價錢一樣, 但係 c 貴過 b, 咁樣野話, (a,b) + c 就會貴過  (a,c) + b; 如果要做到一定得, 咁就要做少少 tracking, effectively 變左同 dijkstra 一樣. 視乎你個 typical order list typically 有幾長, 有機會好大食..