> Задача может быть решена прямым перебором, но мне кажется должны существовать методы либо для решения не комбинаторного, либо для сокращения кол-ва вариантов перебора (например, после сортировки стоимостей пакетов можно отбрасывать дорогие пакеты и т.д.).
> Подскажите, пожалуйста, в какую сторону копать?

Есть тарифные планы с N кол-вом бесплатных минут в день. Если не
израсходовал, то они сгорают. Вообще, опсосы специально вносят сложность
в определение реальной стоимости их услуг.
Я думаю будет слишком сложно найти аналитическое решение данной задачи,
точнее его придется искать снова и снова каждый раз при смене тарифных
планов, доп. услуг и всяческих акций.

Победить эту проблему можно только двумя путями (на мой взгляд).

Первый подход — определить исходные данные как можно более детально, на
математическом языке (например в виде графов, матриц, векторов). Затем
закинуть эти данные на растерзание какому-нибудь математическому пакету
(я бы рассматривал mathematica от wolfram research). А вот все
вычисления, которые будут проводиться этим пакетом над данными
определять на "языке" этого математического пакета, и при этом сами
вычисления будут производными от тарифных планов операторов. Разумеется
каждый раз при смене тарифных планов придется переписывать алгоритм
вычисления (тот, что задан на "языке" мат. пакета).

Второй подход — запустить "эмулятор биллинга" и скоримить ему
вымышленные звонки во всех комбинациях тарифных планов, доп. услуг и
каких-нибудь бонусов. Фактически перебор. При этом "эмулятор биллинга"
придется писать самому, и дописывать его по мере изменения условий у
опсосов.

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

И в том и в другом случае придется подбирать несколько типовых историй
звонков например за месяц.

А, вот еще что. Во втором подходе можно отсортировать комбинации
например по стоимости, и тогда с большой вероятностью самые выгодные
условия будут просчитаны в начале работы алгоритма. Т.е. можно запустить
тотальный пересчет, но приделать возможность отображать промежуточный
вариант. Н-р:
просчитано 12%
результаты:
— немногословный — "план А" + "10 SMS"
— студент — "план А" + "100 SMS" + "интернет"
— тусовщик — "план Б"
— планктон — "план С" + "10 минут в день за 10 рублей"
— комивояжер — "план А" + "безлимитные местные"

Через некоторое время алгоритм дойдет до дорогих планов и может поменять
что-нибудь (например — комивояжеру может оказаться выгоднее какой-нибудь
безлимитный тариф)