寻找适合多个客户的最合适的价格

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或更高。选择这些工作中的哪一个最便宜。