求指點優(yōu)惠券最優(yōu)匹配算法？

問題描述

我這是個優(yōu)惠券的模塊

優(yōu)惠券有3種：指定商品優(yōu)惠券；供應(yīng)商優(yōu)惠券；全場通用優(yōu)惠券；

每個訂單只能使用一張優(yōu)惠券

使用優(yōu)先規(guī)則

1，金額最大并且符合條件優(yōu)先使用

2，金額一樣的話優(yōu)先按指定的商品 - 指定供應(yīng)商 - 全場通用從高至低優(yōu)先級使用

現(xiàn)在假設(shè) 我在購物車同時結(jié)算2個不同供應(yīng)商的商品（不同供應(yīng)商會分訂單）A 和 B ，現(xiàn)在我有2張符合條件的優(yōu)惠券，一張指定A商品的優(yōu)惠券 20元，一張全場通用券30元，按照之前的規(guī)則，會自動選擇A商品使用全場優(yōu)惠券，B就不能使用優(yōu)惠券了。

但是如果A用20的優(yōu)惠券，B也能用通用優(yōu)惠券。我卡在這里了- -

求大佬指點迷津！！我是個小渣渣，我渴望進步！

回答

編輯回答

笨笨噠

說一下算法思路吧, 以下python偽代碼
訂單數(shù)組 A (A0, A1...An) n個，優(yōu)惠券數(shù)組 B (B0,B1...Bm), 其中B0 (金額、類型)，類型：A0~An或c0~ck指定供應(yīng)商或M全場通用。

#用一個hashmap存下來類型數(shù)組, 并用排序
d = {}
for i in B:
    if i[1] in d:
        bisect.insort(d[i[1]], i[0]) #二分法有序插入金額
    else:
        d[i[1]] = [i[0]] # 金額數(shù)組
#時間復(fù)雜度O(mlogk) (k<=m)
#懶得用A的優(yōu)惠券數(shù)組了，A也用hashmap，第一遍給所有的商品分配最高的商品優(yōu)惠券
a = {} #key商品名，value優(yōu)惠券價格
for i in A:
    if i in d:
        a[i] = d[i][0] #最高優(yōu)惠券
        d[i].pop(0)
    else:
        a[i] = 0 #沒有商品優(yōu)惠券0
#時間復(fù)雜度O(n)
#第二遍分組從低到高給所有的商品分配最高的供應(yīng)商優(yōu)惠券
#供應(yīng)商字典C (C0,...Ck) 其中C0的value 是(A0,..At)
for c in C:
    r = sorted([(a[i], i) for i in C[c]], lambda x: x[0]) # 根據(jù)價格排序，同組價格低的排最前面
    if not r:
        continue #沒有這個組不用計算啦
    rindex = 0
    while d[c]: #還有供應(yīng)商優(yōu)惠券
        if d[c][0] <= r[rindex][0]:
            break #比商品優(yōu)惠券低，不要算啦
        a[r[rindex][1]] = d[c][0] #低的商品優(yōu)惠券不要啦，給高的供應(yīng)商優(yōu)惠券
        rindex += 1
        d[c].pop(0)
#時間復(fù)雜度O(k.tlogt)
#最后給全場優(yōu)惠券啦
r = sorted([(a[i], i) for i in a], lambda x: x[0])# 根據(jù)價格排序，價格低的排最前面
rindex = 0
while d['M']: # 有全場通用券
    if d['M'][0] <= r[rindex][0]:
        break #全場通用券太低啦，不要算啦
    a[r[rindex][1]] = d['M'][0] #低的優(yōu)惠券不要啦，給高的全場通用券
    rindex += 1
    d['M'].pop(0)
    
print(a) #最后的結(jié)果啦
#時間復(fù)雜度O(nlogn)

#總得時間復(fù)雜度取決于t、n、m的大小啦

2017年3月31日 02:00

編輯回答