Skip to content

Latest commit

 

History

History
137 lines (83 loc) · 10.2 KB

greedy.md

File metadata and controls

137 lines (83 loc) · 10.2 KB
Raw

Жадный алгоритм

Это не какой-то алгоритм, а скорее простая идея о том, как решаются многие задачи.

Пример задачи: Размен монет

Условие

Есть купюры и монеты номиналами: $1, 5, 10, 50, 100, 1000, 5000$ рублей. В банкомате неограниченное количество купюр каждого номинала. Константин хочет снять со счёта $n$ рублей. Нужно определить минимальное суммарное количество купюр и монет, которое может выдать банкомат, чтобы сумма получилась ровно $n$.

Решение

Выпишем первые несколько ответов на задачу:

ans[1] = 1; # 1
ans[2] = 2; # 1 1
ans[3] = 3; # 1 1 1
ans[4] = 4; # 1 1 1 1
ans[5] = 1; # 5
ans[6] = 2; # 5 1
ans[7] = 3; # 5 1 1
ans[8] = 4; # 5 1 1 1
ans[9] = 5; # 5 1 1 1 1
ans[10] = 1; # 10

Хочется сказать, что оптимальным алгоритмом будет следующее: взять максимум купюр номинала $1000$, из остатка взять максимум купюр номинала $500$ и т.д. Причем это будет верным решением! Такой подход в решении называются "жадностью". А алгоритмы, работающие таким образом, "жадными".

Общая идея жадного алгоритма

В общем смысле жадный алгоритм - это брать элементы в порядке уменьшения чего-нибудь, брать самый большой элемент первым. Эта одна простая идея объединяет множество разных задач.

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

Доказательство решения

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

Вместо того, чтобы доказывать утверждение про жадность для конкретной задачи про числа $1, 5, 10, 50, 100, 1000, 5000$, давайте сформулируем и докажем более сильное:

Если каждый следующий номинал делится на предыдущий, то жадный алгоритм работает.

Доказательство утверждения:

Пусть купюры имели номинал $a_1, \ldots, a_k$. Пусть максимальная купюра имеет достоинство $a_k$ и $a_k < n$, но в оптимальном ответе ее нет. Давайте рассмотрим такой оптимальный ответ и найдем противоречие.

Пусть в оптимальном ответе купюра с номиналом $a_i$ встретилась $b_i$ раз. Если $b \geq \frac{a_{i+1}}{a_i}$ раз, то $\frac{a_{i+1}}{a_i}$ купюр можно легко заменить на одну купюру достоинства $a_{i+1}$, а значит это не оптимальный ответ. Следовательно, $b \leq \frac{a_{i+1}}{a_i} - 1$

Давайте посчитаем, какого достоинства может быть сумма всех достоинств всех купюр в оптимальном ответе, если не считать максимальные купюры. Это будет $$a_1 b_1 + a_2 b_2 + \ldots + a_{k-1} b_{k-1} \leq a_1 (\frac{a_2}{a_1} - 1) + a_2 (\frac{a_3}{a_2} - 1) + \ldots + a_{k-1} (\frac{a_k}{a_{k-1}} - 1) =$$ $$= (a_2 - a_1) + (a_3 - a_2) + \ldots + (a_k - a_{k-1}) = a_k - a_1 < a_k$$

Из этого делаем вывод, что если $n \geq a_k$, то в оптимальный ответ всегда придется взять максмальную купюру размера $a_k$, потому что меньшие купюры просто не смогут оптимальном ответе давать так много. Отсюда и следует корректность жадного алгоритма.

Теперь, когда жадность доказана, можно предъявить алгоритм:


vector<int> n = {1, 2, 5, 10, 50, 100, 1000, 2000, 5000}
int sums, ans = 0;

cin >> sums;
for (int i = 8; i >= 0; i--) {
    ans += sums / n[i];
    sums %= n[i];
}
cout << sums << endl;

Пример задачи: Задача о рюкзаке с делимыми предметами

Условие

Пусть есть рюкзак с вместимостью не более, чем $W$ грамм ($W$ - целое) и $n$ предметов весом $w_i$ грамм и стоимостью $c_i$ за грамм. Мы умеем отрезать от любого предмета целое количество грамм. Требуется набрать рюкзак максимальной стоимости.

Решение

Также будем решать эту задачу жадно. Отсортируем предметы по убыванию "плотности ценности" $\frac{c_i}{w_i}$ и будем брать их жадно. От последнего предмета, который не влезет полностью, возьмем часть.

Доказательство

Давайте представим, что мы уже поделили все предметы на кусочки веса 1 грамм, при этом их ценность стала равна $\frac{c_i}{w_i}$. Понятно, что из кусочков одинакого веса 1 грамм всегда оптимально просто взять кусочки с максимальной ценностью.

Заметим, что в жадном алгоритме мы как раз и набираем максимальные по $\frac{c_i}{w_i}$ кусочки веса 1.

Предьявим алгоритм:

pair<int, int> items[n];

int c, w, W;                 // стоимость и вес предмета 
cin >> W; 
for (int i = 0; i < n; ++i) { 
    cin >> c >> w;
    items[i] = {c, w};
}

sort(items, items + n);

int ans = 0;
for (int i = n - 1; i >= 0; --i) {
    ans += min(items[i].second, W) * items[i].first;
    W -= min(items[i].second, W);
}
cout << ans << endl;

Итоговая асимптотика: $O(n + n\log n) = O(n\log n)$.

Заметим, что если предметы резать нельзя, такой алгоритм не сработает. Как решать задачу для такого случая обсудим на одной из следующих лекций.

Пример задачи: Выбор заявок

Условие

Даны заявки на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия $(s_i$ и $f_i$ для $i$-ой заявки). Нужно из всех заявок оставить как можно больше так, чтобы они не пересекались. При этом если одна заявка закончилась во время $t$, а следующая началась во время $t$, то их можно ставить подряд.

Решение

Здесь жадность становится не такой уже очевидной, потому что неясно в каком порядке рассматривать заявки, те непонятно как "жадно" их набирать.

Давайте посмотрим на самую первую по времени конца заявку. Заметьте, что нам всегда выгодно включить её в оптимальный ответ - она заканчивается раньше всех остальных, а поэтому если в оптимальном ответе самая первая заявка - другая, мы можем безболезненно заменить её на самую первую по времени конца, и новых пересечений не появится, так как мы просто сдвинули самую первую заявку еще левее.

Раз всегда есть оптимальный ответ, в котором выбрана эта самая левая по времени конца заявка, давайте её возьмем, и выберем самую первую по времени конца заявку из оставшихся, не пересекающихся с той.

Из такого рассуждения про одну самую левую по времени конца заявку следует сразу и общее жадное решение задачи - нужно идти слева направо по заявкам, которые отсортированы по времени конца, и брать новую, если можем, то есть если её начало не раньше, чем конец самой последней уже выбранной.

Задание

Вам нужно решить как можно больше задач из этого контеста:

https://informatics.msk.ru/mod/statements/view3.php?id=35449