пятница, 14 октября 2011 г.

Занятие №7. Динамическое программирование с одним параметром

Теория: Лекция                              [Все занятия]

Практика:                                   [Официальная страница]

Учебные задачи:
  
Задача A.
  
[Взрывоопасность]
Очевидно, если N = 1, то возможны два варианта: “А” и “B”. Если N = 2, то можно получить сразу две последовательность, заканчивающиеся на ‘B’, приписав ее к каждой последовательности, получившейся на предыдущем шаге, т.е. последовательности “AB” и “BB”. ‘A’ можно приписать только к одной последовательности “B”, получив “BA”. Итого, для N = 2 получили 3 варианта. Обозначим dp[i] – количество вариантов, которые можно получить из i-блоков. Продолжая рассуждения в той же духе можно заметить, что для любого i можно получить dp[i-1] последовательностей, приписав к ним блок ‘B’, а также dp[i-2] последовательностей, которые заканчиваются на ‘B’, к которым можно приписать блок ‘A’. В итоге получаем рекуррентную формулу dp[i] = dp[i-1] + dp[i-2]. Что является формулой вычисления числе Фибоначчи.
В классическом виде данная задача формулируется так: сколькими способами можно записать последовательность длины N из 0 и 1 без двух подряд идущих нулей. 
   Задача B.
  
[Наибольшая возрастающая подпоследовательность (НВП)]
Данную задачу мы уже решали несколько раз [1C из курса Меньшикова]. Но всегда полезно повторить изученное. В данном решении я привел квадратичное решение. С более быстрым решением можно ознакомится в разборе задачи 1C.
   Задача C.
  
[0-1 Рюкзак]
Классическая задача на ДП, которую нужно уметь решать. На каждом шаге пытаемся набрать вес(j+w[i]), который формируется из веса гарантировано набранного на предыдущих шагах(j) + веса текущей вещи(w[i]). Стоимость такой новой комбинации формируется из стоимости вещей, набранных на предыдущем шаге(dp[j]) + стоимость текущей вещи(p[i]). Если получается так, что новая стоимость для веса j+w[i] более предпочтительна, т.е. превышает стоимость, полученную для этого веса на предыдущих шагах, то нужно обновить ее с учетом i-ой вещи. Суть сказанного иллюстрирует эта строка:

dp[j+ w[i]] = max(dp[j+ w[i]], dp[j] + p[i]);

Отметим тот факт, что изначально весь массив dp заполнен –1, а dp[0] = 0.
Олимпиадные задачи:
  
Задача A.
  
[Покупка билетов]
На каждом этапе пытаемся получить оптимальный ответ для первых N человек. Возможно лучшим решением было бы завести первые три барьерных элемента, но я ручками подсчитал первые три решения для n = 0,1 и 2, а дальше запустил цикл с рекуррентной формулой. 
   Задача B.
  
[Две стены]
Сразу сделаем важную оговорку. Необходимо использовать все кирпичи в наборе. Поэтому если вдруг получилось так, что сумма длин всех кирпичей цвета A не равна сумме длин кирпичей цвета B, значит построить две прямоугольные стены уже не получится. Будем использовать подход, который использовали в решении задачи о рюкзаке. А именно будем искать все возможные комбинации длин, которые можно получить из кирпичей одного цвета. Пусть SUM – сумма длин всех кирпичей одного цвета. Тогда необходимо найти такое значение SEP, что для каждого цвета можно набрать длину SEP и SUM-SEP. Если это сделать удалось, значит решение найдено.
   Задача C.
  
[Репортаж]
Задача легко решается, что мы умеем решать задачу B из предыдущего блока, где нужно находить наибольшую возрастающую подпоследовательность(LIS). Для начала найдем LIS для исходного массива, а потом проделаем тоже самое только LIS будем искать не слева направо, а справа налево. В итоге останется только найти такую позицию в исходном массиве, для которой минимальное значение меньших элементов справа и слева будет максимально.
Дополнительные олимпиадные задачи:
 
Задача A.
  
[Отчет]
Задача сводится к поиску максимальной подпоследовательности, в которой возрастает общий объем производства и убывает процент бракованных изделий. Суть решения мало чем отличается от поиска LIS.
   Задача B.
  
[Словарь]
Для каждой позиции i в тексте будем искать слово, на которое оно может оканчиваться. Для этого можно перебрать все слова(ограничения позволяют) из словаря и проверить можно ли сформировать текст, заканчивающийся позицией i – size, где size – длина текущего слова.
   Задача C.
  
[Валютные махинации]
Несложная задача. Ее можно было дать и в учебных задачах, потому как она позволяет прочувствовать суть ДП на простом примере. Для каждого дня будем искать максимальное количество рублей, долларов и евро, которое можно получить за первые дни, оканчивающихся текущим. Максимальное количество рублей для текущего дня будет равно максимальному из значений:
1) Максимальное количество рублей с предыдущего дня
2) Максимальное количество долларов с предыдущего дня, переведенное по сегодняшнему курсу в рубли. 
3) Максимальное количество евро с предыдущего дня, переведенное по сегодняшнему курсу в рубли.
Доллары и евро ищутся по схожей схеме.

10 комментариев:

  1. "с одним параметроВ".

    ОтветитьУдалить
  2. Извините мне,а я попробавала прочитать условия в тему Рекурсия и получила сообщение Access denied. Где я могу прочитать их? Извините на плохой руский язык

    ОтветитьУдалить
  3. Если речь идет о посте http://cppalgo.blogspot.com/2009/12/blog-post_29.html , то там все задачи ссылаются на ресурс http://dl.gsu.by/ , где нужно ввести логин и пароль. Зайдите по ссылке на этот сайт и зарегистрируйтесь там, после чего сможете пользоваться своей учетной записью.

    ОтветитьУдалить
  4. Я сделала ето, ID 125570, но все таки не успела Опять получаю:
    Access denied
    Access to requested page is denied.
    Typical situations:

    * You are trying to access task which is not opened yet.
    * You are trying to access task in already closed or not yet opened course.
    * You are taking part in competition and trying to access task which is not belongs to this competition.
    * You have finished competition and trying to access task which belongs to this competition.
    * You are trying to access result page during competition which do not allow this.

    If you think that access is denied because of site error, you can post message on forum

    ОтветитьУдалить
  5. У меня к сожалению сейчас не получается зайти на http://dl.gsu.by/ и новый пароль они мне почему-то пока не шлют.

    На сколько я помню после авторизации необходимо найти курс "Алгоритмизация" и подписаться на него. После этого все задачи станут доступными для решения

    ОтветитьУдалить
  6. Спосибо большое, я попробую :)

    ОтветитьУдалить
  7. Добрый день.
    Возможно я ошибаюсь, но для задачи C (про рюкзак) и набора входных данных (1, 3), (3, 2), (2, 2), (4, 6), вместимость рюкзака 9. Не получается получить правильный ответ, использую предоставленный алгоритм. Хотелось бы разобраться в ситуации.

    ОтветитьУдалить
  8. У меня получилась максимальная стоимость 11. Какие вы используете входные данные?

    ОтветитьУдалить
  9. Понял свою ошибку. Получение списка вещей делал некорректно. Спасибо.

    ОтветитьУдалить