ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача про подачу рекламных объявлений
25 сообщений из 30, страница 1 из 2
  1  все
Задача про подачу рекламных объявлений
    #36697061
Sergio Zhizhenko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergio Zhizhenko
Гость
Приветствую.

Жена принесла с работы интересную задачу, для которой я не могу придумать быстрого эффективного решения. Помогите нам, пожалуйста:

1. Есть список из ~80 изданий (газет) с указанием городов, в которых они выходят, и стоимости рекламных блоков в них (как правило каждое издание выходит в 2-10 городах)
2. Есть список целевых городов (около 40), в которых необходимо обязательно подать рекламу

Нужно найти варианты выборки изданий, покрывающих ВСЕ целевые города, упорядоченные по совокупной стоимости подачи рекламы.
...
Рейтинг: 0 / 0
20.06.2010, 17:37:22
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697096
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Задача, как я понимаю, чисто "на интерес", а не практическая?

Точное решение, кажется, находится только перебором. Но есть кое-какие мысли по оптимизации:
1) проверить, нет ли таких городов, где выходит только одна газета, тогда можно удалить (пометить как "решённые") из списков эти города, эти газеты и другие города, которые они покрывают.
2) отсортировать газеты в списке по стоимости в расчете на один покрываемый город и перебор начинать с более дешевых газет.
3) города отсортировать по количеству выходящих в них газет, перебор начинать с менее "покрытых" городов.
...
Рейтинг: 0 / 0
20.06.2010, 18:14:20
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697126
Сомнение
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сомнение
Гость
miksoftЗадача, как я понимаю, чисто "на интерес", а не практическая?

Точное решение, кажется, находится только перебором. Но есть кое-какие мысли по оптимизации:
1) проверить, нет ли таких городов, где выходит только одна газета, тогда можно удалить (пометить как "решённые") из списков эти города, эти газеты и другие города, которые они покрывают.
2) отсортировать газеты в списке по стоимости в расчете на один покрываемый город и перебор начинать с более дешевых газет.
3) города отсортировать по количеству выходящих в них газет, перебор начинать с менее "покрытых" городов.

Я тоже думаю, что перебор здесь подойдёт. Или какой нибудь совершенно невероятный запрос-трюк. Вот по этому поводу у меня как раз созрел вопрос. А нужно ли искать в такой задачи методы оптимизации и тем более трюки? Её по-видимому запускает пользователь максимум раз в день. Ну так может пусть компьютер работает? Даже те чудесные оптимизации что Вы здесь написали не нужны... может?
...
Рейтинг: 0 / 0
20.06.2010, 18:39:10
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697130
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
СомнениеДаже те чудесные оптимизации что Вы здесь написали не нужны... может?Только перебором без оптимизации нельзя. Если совсем тупо подходить к этой задаче, то получится 2 80 комбинаций, что слишком много даже для компьютера.
...
Рейтинг: 0 / 0
20.06.2010, 18:43:10
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697136
Сомнение
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сомнение
Гость
miksoft,

Спасибо. Пойду думать.
...
Рейтинг: 0 / 0
20.06.2010, 18:49:18
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697167
Sergio Zhizhenko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergio Zhizhenko
Гость
miksoftЗадача, как я понимаю, чисто "на интерес", а не практическая?

Задача как раз практическая, до этого ее решали "наугад", подбирая издания вручную и тратя уйму времени, ну и как следствие решения подбирались наверняка не самые оптимальные. Я решил помочь, зайдествовав компьютер )
...
Рейтинг: 0 / 0
20.06.2010, 19:16:29
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697171
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Sergio Zhizhenko,

Тираж, методы распространения, аудитория этих газет не учитывается?
А стоимость рабочего времени сотрудника на контакт с ними?
...
Рейтинг: 0 / 0
20.06.2010, 19:21:00
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697224
Было у меня сомнение
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Было у меня сомнение
Гость
miksoftSergio Zhizhenko,

Тираж, методы распространения, аудитория этих газет не учитывается?
А стоимость рабочего времени сотрудника на контакт с ними?
Вот, за это я люблю форумы. Кто-нибудь легко и походя посоветует подумать на тем над чем никто годами не задумывалася.
...
Рейтинг: 0 / 0
20.06.2010, 20:02:10
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697270
ананисто
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ананисто
Гость
Если я не ошибаюсь, это классическая NP-полная задача.
Точных решений кроме полного перебора (и его вариаций) ещё не найдено.
...
Рейтинг: 0 / 0
20.06.2010, 20:33:11
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697283
Фотография n_string
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
n_string
Участник
Я все-таки склоняюсь, что это bin-pack модель, поскольку условие является определяющим, а упаковка статична.
...
Рейтинг: 0 / 0
20.06.2010, 20:43:01
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697307
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
clihlt
Участник
Sergio Zhizhenko,

Не осилил условие.. Не понятно в одном городе планируется размещать рекламу только в одном издании или возможно размещение рекламы в нескольких изданиях из множества доступных для этого города? И непонятно зачем может понадобится вывод всех возможных вариантов...

В любом случае, если результатом работы алгоритма должны быть все возможные выборки газет - то тут только полный перебор.
Если надо размещать рекламу только в одном издании для одного города, то в худшем случае ( когда каждая газета продается в каждом городе ) это всего навсего 80 * 40 = 3200 комбинаций. Составление массива вариантов покрытий в памяти и последующая его сортировка займут если не доли секунд, то секунды максимум на современном компе.
...
Рейтинг: 0 / 0
20.06.2010, 20:58:05
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697405
Sergio Zhizhenko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergio Zhizhenko
Гость
clihltSergio Zhizhenko,
Не осилил условие.. Не понятно в одном городе планируется размещать рекламу только в одном издании или возможно размещение рекламы в нескольких изданиях из множества доступных для этого города? И непонятно зачем может понадобится вывод всех возможных вариантов...

Главное - покрыть все города. Если в одном городе реклама будет в нескольких изданиях - не страшно (даже исходя из реалий другие варианты врядли возможны, пересечения все-равно будут)

Все возможные варианты я хотел вывести, чтобы их уже вручную обработал оператор, поскольку помимо цены есть еще куча параметров влияющих на оптимальность подачи рекламы (например день выхода газеты и др.) Потому думал вывести варианты отсортировав по цене, а уже человек подберет возможно такой, за который стоит переплатить.
...
Рейтинг: 0 / 0
20.06.2010, 22:22:18
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697417
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
Sergio Zhizhenko
Главное - покрыть все города. Если в одном городе реклама будет в нескольких изданиях - не страшно (даже исходя из реалий другие варианты врядли возможны, пересечения все-равно будут)

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

Если вы дадите мне исходные данные, я покажу, что выдаст моя свеженаписанная софтина. И решите, устроит вас такой подход или нет.
...
Рейтинг: 0 / 0
20.06.2010, 22:28:38
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697426
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
Ну и разумеется, дополнительные критерии оптимальности нужно выбирать ДО поиска решения, а не после.
Потому что решений слишком много.
...
Рейтинг: 0 / 0
20.06.2010, 22:34:34
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697434
Sergio Zhizhenko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergio Zhizhenko
Гость
капитан сикель спешит на помощь
Все возможные варианты считать слишком долго.
А минимально подходящие -- быстро (по критерию уменьшения стоимости при удалении газеты из списка на каждой итерации).

Если вы дадите мне исходные данные, я покажу, что выдаст моя свеженаписанная софтина. И решите, устроит вас такой подход или нет.

Исходные данные разместил в этом архиве .
Сейчас вбиты не все издания (их там в файле 40 вместо 80)
...
Рейтинг: 0 / 0
20.06.2010, 22:39:12
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697436
Sergio Zhizhenko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergio Zhizhenko
Гость
Sergio Zhizhenko
Сейчас вбиты не все издания (их там в файле 40 вместо 80)
Ах, да, важное замечание: изданий-то там в файле много, но рассматривать нужно только те, в которых проставлены данные в колонки тираж и др. (таких как раз около 40)
...
Рейтинг: 0 / 0
20.06.2010, 22:40:58
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697451
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
Sergio Zhizhenko,

По вашему списку нельзя построить удовлетворяющее решение.
Ряд городов не присутствует в списке изданий с ценами (начиная с "Верея").
...
Рейтинг: 0 / 0
20.06.2010, 22:58:12
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697461
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
Sergio Zhizhenko,

Ну а по списку
Код: plaintext
1.
2.
3.
4.
5.
Зеленоград, Воскресенск, Лобня, Королев, Дмитров, Коломна, 
Долгопрудный, Мытищи, Раменское, Ногинск, Пересвет, Истра, 
Яхрома, Реутов, Бронницы, Текстильщики, Красногорск, Монино, 
Сергиев Посад, Нахабино, Юбилейный, Кучино, Волоколамск, 
Хотьково, Балашиха

я получил
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
At [ 71 ] Price =  27210  for total  10 , 
[Альтернатива-кадровый вопрос (Альтернатива), «Альтернатива-кадровый вопрос» - Мытищи:  1440 , 
Альтернатива - все обо всем - Салават:  1210 , 
Волоколамская неделя - Волоколамск:  1130 , 
Все для Вас (ВДВ), «Все для Вас» - Истра:  1490 , 
Х-пресс - Королев:  1450 , 
Квартал СП - Сергиев Посад:  1650 , 
Парад вакансий Северо-Восток - Москва:  4680 , 
Парад вакансий ЮВ - Москва:  4680 , 
Парад вакансий ЮВ - Москва:  4680 , 
В добрый час - Раменское:  4800 ]
...
Рейтинг: 0 / 0
20.06.2010, 23:04:16
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697464
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
И, разумеется, это вовсе не полное и не точное решение задачи.
А очень быстрое и очень приблизительное.
...
Рейтинг: 0 / 0
20.06.2010, 23:08:03
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697470
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
Также весьма забавно, что решение отличается от запуска к запуску из-за случайного накопления коллекции изданий:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Found total  9  for  18950 
Парад вакансий ЮВ - Москва:  4680 
Волоколамская неделя - Волоколамск:  1130 
Альтернатива-кадровый вопрос (Альтернатива), «Альтернатива-кадровый вопрос» - Мытищи:  1440 
Парад вакансий ЮВ - Москва:  4680 
Бойкое место - Бронницы:  1600 
Все для Вас (ВДВ), «Все для Вас» - Истра:  1490 
Квартал СП - Сергиев Посад:  1650 
Королевский экспресс - Королев:  1070 
Альтернатива - все обо всем - Салават:  1210
...
Рейтинг: 0 / 0
20.06.2010, 23:12:23
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36697886
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
Sergio Zhizhenko,

Минимально повторяемое решение:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Total calculations:  5886121 
Found total  9  for  18650 
Альтернатива-кадровый вопрос (Альтернатива), «Альтернатива-кадровый вопрос» - Мытищи:  1440 
Все для Вас (ВДВ), «Все для Вас» - Истра:  1490 
Квартал СП - Сергиев Посад:  1650 
Истра сегодня - Истра:  1723 
Парад вакансий ЮВ - Москва:  4680 
Королевский экспресс - Королев:  1070 
Альтернатива - все обо всем - Салават:  1210 
Парад вакансий ЮВ - Москва:  4680 
Бойкое место - Бронницы:  1600
...
Рейтинг: 0 / 0
21.06.2010, 11:16:47
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36698827
ах дамы, господа
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ах дамы, господа
Гость
Sergio ZhizhenkoПриветствую.

Жена принесла с работы интересную задачу, для которой я не могу придумать быстрого эффективного решения. Помогите нам, пожалуйста:

1. Есть список из ~80 изданий (газет) с указанием городов, в которых они выходят, и стоимости рекламных блоков в них (как правило каждое издание выходит в 2-10 городах)
2. Есть список целевых городов (около 40), в которых необходимо обязательно подать рекламу

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

дано:
map<key=газета, value= список городов>;
список нужных городов;

решение:
1)преобразовать в map<key = нужный город(40) , value=список газет города>
2)сделать список из 40-элементных сочетаний газет из value этой мапы
3)получившийся список упорядочить по общей стоимости
...
Рейтинг: 0 / 0
21.06.2010, 17:01:02
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36698852
ах дамы, господа
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ах дамы, господа
Гость
как видно, среднее быстродействие зависит от количества газет, приходящихся в среднем на 1 город
...
Рейтинг: 0 / 0
21.06.2010, 17:07:53
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36699087
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
ах дамы, господа,

Или ты не понимаешь вычислительной сложности задачи, или одно из двух.
Издание выходит в 2-10 городах.
Всего 80 изданий.
40 городов.

Посчитай количество допустимых комбинаций на досуге.
...
Рейтинг: 0 / 0
21.06.2010, 18:48:18
| Ответить | Цитировать | Написать  
Задача про подачу рекламных объявлений
    #36699097
капитан сикель спешит на помощь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
капитан сикель спешит на помощь
Гость
И, разумеется, общее количество изданий, которыми покрываются все 40 городов, также разное.
...
Рейтинг: 0 / 0
21.06.2010, 18:53:17
| Ответить | Цитировать | Написать  
25 сообщений из 30, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача про подачу рекламных объявлений
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36697136&tid=1343607]:
 0ms
get settings:
 8ms
get forum list:
 13ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 186ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 76ms
get tp. blocked users:
 1ms
others: 221ms
total:  520ms
созд. / загр.: 520ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]