ВОКРУГ ЖАДНЫХ АЛГОРИТМОВ

Жадность – это правильно хорошо!
Даже если неправильно.


Gordon Gekko
Igor Mazurok

ПОПЫТКА ПЛАНА

  • Вычислительная сложность алгоритмов
  • Интуитивное представление о жадных алгоритмах
  • Примеры
  • Код Хафмана
  • Матроиды как математическая модель жадности
  • Прим против Краскала http://mist.codelands.com/
  • Реализация очереди с приоритетами
  • Существует ли алгоритм поиска максимального элемента массива?
  • Бинарная куча

ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ АЛГОРИТМОВ

  • O(1)
  • ---------------------
  • O(log n)
  • O(n)
  • O(n . log n)
  • ---------------------
  • O(P(n))
  • ---------------------
  • O(en)
  • O(n!)

ХОРОШИЕ И ПЛОХИЕ АЛГОРИТМЫ

N2 = 1000 N1 – Размер увеличился в 1000 раз

  • O(log n):
    T1 ~ log N1
    T2 ~ log N2 ~ log (1000 * N1) ~ log1000 + log N1 ~ log1000 + T1 - увеличилось «НА» …
  • O(n):
    T1 ~ N1
    T2 ~ N2 ~ 1000 * N1 ~ 1000 * N1 ~ 1000 * T1 - время увеличится «ВО» столько раз

N2 = 1 + N1 – Размер увеличился на 1

  • O(en):
    T1 ~ e
    N1
    T2 ~ e
    N2 ~ e1+N1 ~ e * eN1 ~ e * T1 – время увеличится «В» несколько раз

ЗАДАЧА САВВЫ МОРОЗОВА

Дано:

  • N – напитков
  • C[i] – стоимость
  • V[i] – ёмкость

Нужно:

Наполнить ёмкость объёма V

Sum{v[i] * C [i] / V[i], v[i] ∈ V} → max

При условии v[i] <= V[i]

Решение:

Пока V>0 и V[i] > 0

  • v[j] = min{V, V[i]}
  • V -= v[i]
  • V[i] -= v[i]
  • Если V==0, то решили, иначе – нет.

ЗАДАЧА БРАТА АЛИ-БАБЫ

Дано:

  • N – сокровищ
  • C[i] – стоимость
  • V[i] – вес

Нужно:

Нагрузить ослика грузоподъёмностью V

Sum{v[i] * C [i] / V[i], v ∈ V} → max

При условии v[i] ∈ {V[i], 0}

Решение:

ВОПРОС

  • Почему Савва Морозов может жадничать, а брат Али-Бабы нет?

VS

ЗАДАЧА А

5

7

8

1

2

9

5

2

4

В каждой строке выбрать не более одной ячейки.

Сумма чисел в выбранных ячейках должна быть максимальной

ЗАДАЧА В

2

3

8

1

2

9

2

5

7

В каждой строке и столбце выбрать не более одной ячейки.

Сумма чисел в выбранных ячейках должна быть максимальной

МАТРОИДЫ

  • X - конечное множество, называемое носителем матроида
  • I ⊃ 2X  - семейством независимых множеств (множество подмножеств X)
  • Матроид M = (X,I)
    • ∅∈I
    • A∈I, B ⊃ A ➔ B ∈ I
    • A ∈I, B ∈I, |A|>|B| ➔ ꓱ x ∈ A\B: B ∪ {x} ∈ I

Оптимизация на независимых множествах может быть жадной

    • Матричный матроид
    • Графовый матроид

МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО

  • Проблема. Как не создать цикл?
  • Прим. Предполагаем в начале, что находимся в некоторой вершине. С жадностью присоединяем самое короткое ребро, ведущее отсюда куда-нибудь ещё и расширяем понятие «отсюда».
  • Краскал. Предполагаем в начале, что ребер нет и есть только вершины-острова. С жадностью добавляем самое короткое ребро, объединяющее два острова.
  • http://mist.codelands.com/

ПОИСК МИНИМУМА В МАССИВЕ

БИНАРНАЯ КУЧА

struct mycomp {

bool operator()(const long& a, const long& b) {

return a>b;

}

};

priority_queue < long, vector <long>, mycomp > x;

x.push(num);

x.top();

x.pop();

Армреслинг

Сила членов двух команд точно измерена.

Необходимо составить пары для поединков.

В максимальном числе боев должна победить заданная команда.

Сортируем игроков по убыванию силы.

Перебираем игроков нужной команды от сильных к слабым.

Каждому находим наиболее сильного (но слабее) соперника.

Если такого не нашлось, то далее назначаем любого.

Odd Team: 9 7 5 3 1 Какая команда наберет больше побед?

Even Team: 8 6 4 2 0

РЕШАЕМ ЗАДАЧИ

Бензоколонки
e-olymp.com/ru/problems/4211

Вдоль кольцевого шоссе длины L расположено n бензоколонок. В первой строке заданы L и n. Во второй - n различных целых чисел – позиции бензоколонок.

Вывести максимально возможное расстояние по шоссе до ближайшей бензоколонки (с точностью 1 знак после запятой).

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace
std;
int
main() {
int l, n, max_distance;
cin >> l >> n;
int x[n];
for(int i =
0; i < n; ++i) cin >> x[i];
sort(x, x+n);
max_distance = l - x[n-
1] + x[0];
for(int i =
1; i < n; ++i)
max_distance = max(max_distance, x[i] - x[i-
1]);
cout << max_distance / 2 << (max_distance % 2? ".5" : ".0") << endl;
return
0;
}

Где тут жадность?

Призыв в армию
e-olymp.com/ru/problems/182

Для похода Оргрим потребовался отряд. На призыв явились n орков. Способности в ближнем бою и метании копья каждого из них он сразу же оценил. Теперь же нужно разделить их на пехотинцев (grunt) и охотников за головами (headhunter). При этом необходимо, чтобы в отряде было не менее g грунтов и не менее h хедхантеров. Сила отряда определена, как сумма способностей всех орков в назначенной им специализации. Определите максимально силу отряда.

#include <iostream>

#include <algorithm>

using namespace std;

struct orc { int g, h; } x[10000];

bool compare(orc a, orc b) {

return (a.g - a.h) < (b.g - b.h);

}

int main() {

int n, g, h;;

cin >> n >> g >> h;

if (n < g + h) {

cout << "-1\n";

return 0;

}

for (int i = 0; i < n; i++) {

cin >> x[i].g;

cin >> x[i].h;

}

sort(x, x + n, compare);

int p = 0;

for (int i = 0; i < n; i++) {

if (i < h) p += x[i].h;

else if (i < n-g) p += x[i].h > x[i].g ? x[i].h : x[i].g;

else p += x[i].g;

}

cout << p << endl;

}

  • Где тут жадность?
  • Как сравнивают орков?
  • Какой вопрос третий?

Задача сапожника
e-olymp.com/ru/problems/1591

Сапожнику необходимо выполнить n работ. Для каждой i-ой работы известно время ее выполнения в днях Ti и штраф Si, который каждый день должен платить сапожник до тех пор, пока он не отдаст i-ую работу заказчику. Начав работу ее нужно довести до конца.

Найти последовательность выполнения работ, при которой сумма штрафов будет минимальной. Из нескольких оптимальных порядков работ выводить лексикографически наименьший.

#include <iostream>

#include <algorithm>

using namespace std;

int next = 0;

struct task {

int t, s, i;

task () {

cin >> t >> s;

i = ++::next;

}

};

int compare(task x, task y) {

return x.t * y.s < x.s * y.t;

}

int main() {

for (int n = 0; cin >> n; ) {

int t, s;

task *x;

x = new task[n];

stable_sort(x, x+n, compare);

cout << x[0].i;

for(int i = 1; i < n; i++) cout << " " << x[i].i;

cout << endl;

delete[] x;

::next = 0;

}

}

  • Где тут жадность?
  • Где вводятся заявки?
  • Почему ::next?
  • Почему наше решение не в топе?
  • Почему, собственно, stable_sort?

Недавно Сергей пошел к колодцу за водой, но так и не вернулся. Он взял с собой n канистр, каждую из которых он полностью наполнил водой. Теперь Сергей хочет доставить их в свой загородный дом. Вот в этом и заключается проблема. За один раз Сергей может унести не более 2 канистр - у него ведь всего две руки. Более того, он может нести не более k литров воды. За какое минимальное число раз Сергей сможет отнести всю воду домой, и может ли вообще.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace
std;

int
main() {
std::ios::sync_with_stdio(false);
unsigned n, k;
cin >> n >> k;
unsigned *x = new unsigned [n];
for(unsigned i =
0; i < n; i++) {
cin >> x[i];
if (x[i] > k) {
cout << "Impossible\n";
return
0;
}
}
sort(x,x+n,[](int a, int b) {return a > b;});
unsigned i =
0, j = n - 1;
while (i <= j) {
if (x[i] + x[j] <= k) j--;
i++;
}
cout << i << endl;
return
0;
}

  • Где тут жадность?
  • Почему тяжелое объединяют с легким?
  • Почему наше решение не в топе?

Прием у директора
e-olymp.com/ru/problems/66

Имеется множество заявок на посещение директора с указанием времени начала и конца каждого. Заявки могут накладываться.

Найти максимальное количество посетителей, которое сможет принять директор без накладок.

#include <iostream>

#include <algorithm>

using namespace std;

int get_time() {

int h, m;

cin >> h; cin.ignore(); cin >> m;

return h * 60 + m;

}

struct visit {

int from, to;

visit () { from = get_time(); to = get_time(); }

};

int main() {

int n, k = 0, prev = 0;

cin >> n;

visit x[n];

sort(x, x + n, [](const visit & x, const visit & y){return x.from < y.from;});

for (int i = 1; i < n; ++i) {

for (int j = prev; j < n; ++j) {

if (x[i].from >= x[j].to) {

k++;

prev = i;

break;

} } }

cout << ++k << endl;

return 0;

}

  • Где тут жадность?
  • Где вводятся заявки?
  • Как ускорить работу?

Добавить все
e-olymp.com/ru/problems/1228

Стоимость сложения С двух чисел равна их сумме. Например, сложить числа 1 и 10 стоит 11.

Складывать числа можно разными способами. Например, для 1 + 2 + 3 имеем:

1 + 2 = 3 (С = 3), 3 + 3 = 6 (С = 6), ∑ = 9.

1 + 3 = 4 (С = 4), 2 + 4 = 6 (С = 6), = 10.

2 + 3 = 5 (С = 5), 1 + 5 = 6 (С = 6), = 11.

Вывести наименьшую стоимость сложения всех чисел.

//#include <functional>?

#include <iostream>

#include <queue>

using namespace std;

priority_queue <long, vector<long>, greater<long> > x;

int main() {

long n, num;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> num;

x.push(num);

}

long res = 0;

while (x.size() > 1) {

long a, b;

a = x.top();

x.pop();

b = x.top();

x.pop();

x.push(a + b);

res += a + b;

}

cout << res;

return 0;

}

  • Где тут жадность?
  • А где, собственно, алгоритм?
  • Что делает priority_queue?

#include <iostream>

#include <queue>

using namespace std;

struct mycomparator {

bool operator()(const long & a, const long & b) {

return a > b;

} };

priority_queue<long, vector<long>, mycomparator > x;

int main() {

long n, num, res = 0;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> num;

x.push(num);

}

while (x.size() > 1) {

long a, b;

a = x.top(); x.pop();

b = x.top(); x.pop();

x.push(a + b);

res += a + b;

}

cout << res;

return 0;

}

Земли Антарктиды
e-olymp.com/problems/1685

На карте Антарктики
точками изображено
n полярных станций, каждая из которых имеет натуральные координаты в прямоугольной сетке. Переход между двумя станциями возможен, если расстояние между ними по прямой меньше двух. Станции, между которыми существует прямое или транзитное соединение, объединяются в земли, и каждая станция принадлежит только одной земле.
Определить количество земель.

class EOlymp1685 {
static int SIZE = 102;
static int antarctida[][] = new int [SIZE][SIZE];
static void repaint(int from, int to) { // repaint connected lends
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (antarctida[i][j] == from) antarctida[i][j] = to;
} } }
public static void main (String[] args) throws java.lang.Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int k = 1; k <= n; k++) {
int x = in.nextInt(); int y = in.nextInt();
// paint near
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (antarctida[i][j] != 0 && antarctida[i][j] != k) {
repaint(antarctida[i][j], k);
} } }
antarctida[x][y] = k;
}
// count lands
boolean lands[] = new boolean[n+1];
int count = 0;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (!lands[antarctida[i][j]]) {
lands[antarctida[i][j]] = true;
count++;
} } }
System.out.println(count-1);
} }

  • Где тут жадность?
  • Как ускорить алгоритм?
  • Какой третий вопрос?

В банкомате имеются в достаточном количестве купюры номиналом 10, 20, 50, 100, 200 и 500 гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n гривен или вывести -1, если указанную сумму выдать нельзя.

class EOlymp138
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
int n = in.nextInt(), count =
0, many[] = {500, 200, 100, 50, 20, 10};
for (int i =
0; i < many.length; i++) {
count += n / many[i];
n %= many[i];
}
System.out.println(n >
0? -1: count);
}
}

  • Где тут жадность?
  • Для любого ли набора купюр работает такая схема? Например, 11, 5 и 1 для 15-и?
  • Каким условиям должен удовлетворять набор купюр, чтобы образовался матроид?

Новогодние подарки
e-olymp.com/ru/problems/26

Деду Морозу и Снегурочке нужно доставить n подарков детям. Зная время t1 упаковки каждого подарка Снегурочкой и время его доставки Дедом Морозом t2, вычислить наименьшее время, необходимое для выполнения всех заказов. В свой мешок Дед Мороз может положить только один подарок.

#include <iostream>

#include <algorithm>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {

return min(a.first, a.second) < min(b.first, b.second);

}

int main() {

int n; cin >> n;

pair<int, int> a[n];

for(int i = 0; i < n; i++) cin >> a[i].first;

for(int i = 0; i < n; i++) cin >> a[i].second;

sort(a, a + n, cmp);

pair<int, int> arr[n];

int i = 0, j = n - 1;

for(int k = 0; k < n; k++) {

if(a[k].first < a[k].second) arr[i++] = a[k];

else arr[j--] = a[k];

}

int ans = 0, fir = 0;

for(int i = 0; i < n; i++) {

fir += arr[i].first;

ans = max(ans, fir) + arr[i].second;

}

cout << ans << endl;

return 0;

}

Стабильное бракосочетание
e-olymp.com/ru/problems/796

#include<cstring>

#include<queue>

#include<cstdio>

#include<algorithm>

#define N 30

using namespace std;

int couple, malelike[N][N], femalelike[N][N], malechoice[N], femalechoice[N], malename[N], femalename[N];

char str[N];

queue<int>freemale;

int main(){

int t; scanf("%d", &t);

while (t--) {

scanf("%d", &couple);

while (!freemale.empty()) freemale.pop();

for (int i = 0; i < couple; i++){

scanf("%s", str);

malename[i] = str[0] - 'a';

freemale.push(malename[i]);

}

sort(malename, malename + couple);

for (int i = 0; i < couple; i++){

scanf("%s", str);

femalename[i] = str[0] - 'A';

}

for (int i = 0; i < couple; i++){

scanf("%s", str);

for (int j = 0; j < couple; j++) malelike[i][j] = str[j + 2] - 'A';

}

for (int i = 0; i < couple; i++){

scanf("%s", str);

for (int j = 0; j < couple; j++) femalelike[i][str[j + 2] - 'a'] = couple - j;

femalelike[i][couple] = 0;

}

memset(malechoice, 0, sizeof(malechoice));

for (int i = 0; i<couple; i++) femalechoice[i] = couple;

while (!freemale.empty()){

int male = freemale.front();

int female = malelike[male][malechoice[male]];

if (femalelike[female][male]>femalelike[female][femalechoice[female]]){

freemale.pop();

if (femalechoice[female] != couple){

freemale.push(femalechoice[female]);

malechoice[femalechoice[female]]++;

}

femalechoice[female] = male;

}

else malechoice[male]++;

}

for (int i = 0; i < couple; i++)

printf("%c %c\n", malename[i] + 'a', malelike[malename[i]][malechoice[malename[i]]] + 'A');

puts("");

}

}

Что решать дальше?

Вокруг жадных алгоритмов - Google Slides