Это не какой-то алгоритм, а скорее простая идея о том, как решаются многие задачи.
Есть купюры и монеты номиналами: \(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