價格批量折扣算法

Question

我正在設計一箇中國拍賣網站。

門票（$ 5，$ 10 & $ 20）可以單獨銷售，也可以通過套餐獲得折扣。 有各種票的包例如：

1. 5- $ 5張=接收10％的折扣
2. 5- $ 10門票=接收10％的折扣
3. 5- $ 20張票=接收10％的折扣
4. 5- $ 5張+ 5- $ 10張+ 5- $ 20張票=接收15％的折扣

當用戶添加門票其車，我需要找出最便宜的包（多個）給他們。訣竅是，如果用戶添加4-5美元的門票+ 5-10美元的門票+ 5-20美元的門票，它應該仍然給他包4，因爲這對他來說是最便宜的。

任何幫助找出算法來解決這個問題，或任何提示將不勝感激。

感謝

編輯

我想出了答案，感謝所有，但代碼很長。

如果有人仍然有興趣，我會發布答案代碼。

Answer 1

一種方法是動態編程。

的想法是，如果買方希望項目A X，B項的Y和C項Z，那麼你應該計算所有三元組（X 'Y'，Z'）0 < = X '< = x和0 < = Y' < = y和0 < = Z '< = Z，以獲得至少爲x最便宜的方式' A的，Y 'B，和Z' 的C.僞代碼：

for x' = 0 to x 
    for y' = 0 to y 
     for z' = 0 to z 
      cheapest[(x', y', z')] = min over all packages p of (price(p) + cheapest[residual demand after buying p]) 
      next_package[(x', y', z')] = the best package p 

然後，您可以從（x，y，z）向next_package指示的包添加到購物車。

如果有很多不同種類的物品或每個物品有很多，分支和邊界可能是更好的選擇。

Answer 2

首先，計算你需要多少滿包4。讓他們走開。

full_package_4_count = min(x, y, z) mod 5. 

x = x - 5 * full_package_4_count 
y = y - 5 * full_package_4_count 
z = z - 5 * full_package_4_count 

現在，仍有可能是值得買一些包裝4S，即使他們實際上並沒有想買，很多票。

其中可能有多少？

partial_package_4_max = (max(x, y, z) + 4) mod 5 

現在循環，每一項嘗試：

best_price = 10000000 
for partial_package_4_count = 0 to partial_package_4_max: 
    -- Calculate how much we have already spent. 
    price = (full_package_4_count + partial_package_4_count) * 175 * (1-0.15) 

    -- Work out how many additional tickets we want. 
    x' = max(0, x - 5 * partial_package_count) 
    y' = max(0, y - 5 * partial_package_count) 
    z' = max(0, z - 5 * partial_package_count) 

    --- Add cost for additional tickets (with a 10% discount for every pack of 5) 
    price = price + x' mod 5 * 25 * (1-0.10) + x' div 5 * 5 
    price = price + y' mod 5 * 50 * (1-0.10) + x' div 5 * 10 
    price = price + y' mod 5 * 100 * (1-0.10) + x' div 5 * 20 

    if price < best_price 
     best_price = price 
     -- Should record other details about the current deal here too. 

Answer 3

銷售客戶儘可能多的完整包儘可能之後，我們剩下的期望每個3種門票的一些殘量（5美元，10美元，20美元）。在你給出的例子中，所需的數量範圍從0到5（6個可能的值）。因此，只有214個可能的殘差組合（6 ** 3-2;減2，因爲0-0-0和5-5-5組合是退化的）。只需預先計算每種組合的價格，就好像它是在沒有包裝4的情況下購買一樣;將這種計算與第4包（148.75美元）的費用進行比較;這會告訴你每種組合最便宜的方法。

包的實際數量如此之大以至於完整的預計算並不是一種可行的方法？