Поиск оптимальной цены для нескольких клиентов

Question

Пересчет сравнения нескольких вариантов цены для многих клиентов алгоритмически, без излишних затрат.

У нас есть 1000 000 клиентов. Стоимость проданных товаров для каждого из них может быть выражена как цена A или цена B.

Цена А << Цена Б.

Цена A и Цена B не являются линейными по отношению друг к другу. В некоторых случаях B стоит в 2 раза дороже, в некоторых - в 100 раз.

Стоимость всех клиентов на А составляет

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

По сути, средняя стоимость всех клиентов на A будет округлена до 100, если она меньше 100.

На Б. такого ограничения нет

Я хотел бы потратить наименьшую сумму денег на свои товары.

Как мне максимизировать

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

Я продолжаю видеть это как форму двойной проблемы ранца, но я не могу понять это правильно...

Скорее всего, я бы решил это на Python, хотя я сомневаюсь, что это имеет большое значение.

Я провел ручной анализ, присваивая баллы xyz и фильтруя их, меня интересует больше вычислительных решений.

Любые подходы, чтобы рекомендовать?

Answer 1

Каждому клиенту может быть назначена сторона A или сторона B. Если я передам вам наилучшее из возможных решений, вы обнаружите, что вы не можете улучшить его, изменив назначение какого-либо одного клиента. Учитывая это, есть два случая, чтобы проверить, могу ли я игнорировать пограничный случай:

1) В лучшем решении средняя стоимость клиентов на стороне А составляет не менее 100, поэтому минимальная цена не вступает в силу. Если я переключаю покупателя с А на Б или наоборот, стоимость меняется на разницу в ценах А и Б для этого покупателя. Поскольку у меня есть идеальное решение, каждый клиент должен быть назначен на ту, у которой стоимость А или В меньше, что в вашем случае означает, что все идут к А.

2) На стороне A действует минимальная плата в размере 100 на каждого клиента, поэтому изменение клиента с A и B или наоборот означает взимание с него стоимости 100 за A. Поскольку у меня есть идеальное решение, клиенты на 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 этого клиента, но вам все равно придется платить цену B по крайней мере 100, поэтому здесь тоже нечего приобретать.

Поэтому я думаю, что вы рассчитываете стоимость двух возможностей: в случае 1 вы назначаете все для A, а в случае 2 вы назначаете вещи для A, где цена B составляет 100 или более. Выбрал, какая из этих работ дешевле.