尋找適合多個客戶的最合適的價格

Question

Comparing multiple price options for many customers algorithmically的重述幾乎沒有那麼多。

我們有1,000,000位顧客。 爲他們每個人的出售商品的成本可以被表達爲價格A或B.價格

價A < <價格B.

價A及價B不是線性到彼此。在某些情況下，B是2倍昂貴，有些則是100倍。上的所有客戶的

成本

min((sum(A)/count(A)) , 100) * count(A) 

實際上，上的所有客戶將被調高至100的平均成本，如果低於100

沒有對B的這種限制。

我想花最少的錢在他們的貨物上。

如何最大化

cost=min((sum(A)/count(A)) , 100) * count(A) + sum(B) 

我一直看到這是一個雙揹包問題的一種形式，但我不能得到它的權利......

我會可能解決這個在Python中，很可能，儘管我懷疑這很重要。

我已經完成了手動分析，將分數分配給x y z並基於此進行過濾，我對更多的計算解決方案感興趣。

任何建議的方法？

Answer 1

可以將每個客戶分配到A方或B方。如果我把最好的解決方案交給你，你會發現你不能通過改變任何一個客戶的任務來改進它。鑑於此，有兩種情況需要檢查，如果我可以忽略臨界情況：

1）在最佳解決方案中，A方客戶的平均成本至少爲100，因此最低價格不會生效。如果我將客戶從A轉換到B，反之亦然，則該客戶的A和B價格差異會導致成本更改。由於我有一個完美的解決方案，每個客戶都必須分配到A或B成本較低的那一個，在您的情況下意味着每個人都去A。

2）每位客戶的最低100個收費對A方面，如果將客戶從A和B變更或反之，則相當於爲A收取100元的成本。由於我有一個完美的解決方案，因此A方的客戶必須是B價格至少爲100的客戶，而B方的顧客必須是B價爲100或更低的顧客。

這裏唯一的問題是如果切換客戶意味着100最小值生效或停止生效。在（1）如果有人切換到B的情況下，即使A價格沒有最小生效，價格也會增加，所以這不會發生。 （2）如果B方客戶轉向A，這隻能使情況更糟，因爲他們的B價格是100或更低，所以他們的A價格必須是100或更低。 A顧客的B價格必須在100以上。如果他們的A價格是100或更高，他們肯定應該停留在A上，因爲將他們移動到B不能使最低成本停止應用。如果他們的A價格是< 100並且將他們移動到B停止了踢腿的最低A價格，那麼您將爲該客戶的真實A價格支付更少的費用，但是您仍然必須支付至少100的B價格，所以那裏在這裏也沒有什麼可以獲得的。

因此，我認爲你可以計算出兩種可能性的成本 - 情況1是將所有內容分配給A的情況，情況2是將內容分配給A的情況，其中B的價格爲100或更高。選擇這些工作中的哪一個最便宜。