This question is an exact duplicate of:
A restatement of Comparing multiple price options for many customers algorithmically without nearly as much cruft.
We have 1,000,000 customers. The cost of goods sold for each of them can be expressed as price A or price B.
Price A << Price B.
Price A and Price B are not linear to each other. In some cases B is 2 times as expensive, in some it is 100 times.
cost of all the customers on A is
min( (sum(A)/count(A)) , 100 ) * count(A)
Effectively, the average cost of all the customers on A will be rounded up to 100 if it is less than 100.
There is no such restriction on B.
I would like to spend the least amount of money on their goods.
How do I maximize
cost=min( (sum(A)/count(A)) , 100 ) * count(A) + sum(B)
I keep seeing this as a form of a dual knapsack problem, but I can't get it right ...
I'd be probably solving this in Python, most likely, although I doubt that matters much.
I've done manual analyses by assigning scores to x y z and filtering based upon that, I'm interested in more of a computational solution.
Any approaches to recommend?