Здравствуйте, Zlobnyi Serg, Вы писали:

ZS>Добрый день!

ZS>Жена принесла с работы интересную задачу, для которой я не могу придумать быстрого эффективного решения. Помогите нам, пожалуйста:
ZS>Нужно найти варианты выборки изданий, покрывающих ВСЕ целевые города, упорядоченные по совокупной стоимости подачи рекламы.

Думаю, что одновременно точного и эффективного решения нет.
Вот что пришло в голову. Может что-то поможет:

Вариант 1. Точное решение, но не эффективное

а) определяем максимальную возможную стоимость рекламной компании (т.е. если все издания используем)
б) для каждого X из отрезка [0,максимальной стоимости] подбираем комплект изданий в сумме дающие по стоимости X
в) если комплект изданий покрыл все целевые города, то выводим решение. Если нет двигаемся дальше

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

Вариант 2. Метод Монте-карло — не точное и быстрое.

а) Для каждого издания вводим некую характеристику "качества". Например (стоимость/количество городов).
б) Случайным образом выбираем издание для использования (издание с лучшим качеством выбираются чаше)
в) Повторяем п."б" пока не будут покрыты все целевые города. Фиксируем результат
г) После некоторого количества (несколько миллионов и больше) повторов (а лучше даже в режиме реального времени) выводим лучшие N решений

Еще можно использовать Генетические алгоритмы — для таких задач очень хорошо подходят. И вроде нетрудно придумать операции мутации и скрещивания.
Должно получиться более точно, чем вариант 2. И также быстро.