ACM problems/solutions (SouthEastern European Regional Contest, problem I)
http://acm.ro/2009/index.html
http://acm.ro/2009/prob/ACMproblems2009.zip
(копия http://acm.voroh.com/acm_ro_2009/ACMproblems2009.zip)
Задача I
http://acm.ro/2009/prob/probleme/I.pdf
(копия http://acm.voroh.com/acm_ro_2009/I.pdf )
решение: http://acm.voroh.com/acm_ro_2009/I2009.CPP
Насколько я знаю, такого рода задача может решаться двумя способами: либо перебором, либо методами динамического программирования. Размерность M <= 10^9 сразу навела на мысль, что для динамического программирования явно не хватит памяти. Возможно, тут и есть какие-то перспективы, но я от этого подхода отказался. Ограничение N <= 15, напротив, внушало оптимизм в плане применения перебора. Но все оказалось не так просто. Реализованный «в лоб» перебор работал слишком медленно. Пришлось искать отсечения, которые уменьшили бы дерево поиска.
В процессе поиска поочередно рассматриваем все ящики с алмазами, из каждого выбирается от 0 до k алмазов (как это и определено условием задачи). Применяются отсечения следующего характера:
1. Если в процессе поиска мы приходим к такой ситуации, когда оставшегося свободного места (веса) хватает на все оставшиеся алмазы из нерассмотренных ящиков плюс некоторое количество x алмазов из рассматриваемого в данный момент ящика, то мы забираем все x алмазов из текущего ящика.
2. На каждом из шагов мы оцениваем сверху возможную стоимость выбранных алмазов, и если она меньше текущей максимальной стоимости (полученной ранее), то идти вперед нет смысла, и делается шаг назад. Оценка сверху вычисляется, как произведение оставшегося свободного места (веса) на максимальную удельную стоимость (стоимость делить на вес) алмазов из оставшихся ящиков. Может быть, можно применить и какие-то более сложные и более точные оценки, но я ограничился этой.
Для того, чтобы использовать этот факт эффективнее, мы первоначально вычисляем при помощи некоторой эвристики значение максимальной стоимости алмазов, которые можно унести (вернее, получаем ее ограничение снизу) и используем это значение в дальнейшем в процессе поиска.
Это отсечение наиболее значительно сократило время работы программы.
3. Если для некоторых двух ящиков i и j (считаем, что i<j, и ящики в процессе поиска рассматриваются в порядке возрастания их номеров) выполнено: w[i] <= w[j] и c[i] >= c[j], то брать алмазы из ящика j имеет смысл только тогда, когда уже взято максимальное количество алмазов из ящика i.
4. Если для некоторых двух ящиков i и j (считаем, что i<j, и ящики в процессе поиска рассматриваются в порядке возрастания их номеров) выполнено: w[i] >= w[j] и c[i] <= c[j], и из ящика i взято ненулевое количество алмазов, то брать алмазы из ящика j имеет смысл только все.
В итоге программа на не очень быстрой машине проходит тесты за время около 1,5 секунд. Думаю, что это более-менее удобоваримый результат.
Согласно данным acm.ro , эту задачу на олимпиаде не решила ни одна команда. Думаю, что это не удивительно, потому что, во-первых, я сам решал ее пару дней, имя под рукой тесты :) (хотя это, конечно, не показатель), а во-вторых, абсолютно не факт, что данный перебор с данными отсечениями будет работать за приемлемое время на произвольных входных данных. Но, тем не менее, программа работает, тесты проходит… :)
