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

замечания

Проблема с непрерывным рюкзаком

Приведенные предметы как (value, weight) нам нужно поместить их в рюкзак (контейнер) емкости k . Заметка! Мы можем сломать элементы, чтобы максимизировать ценность!

Пример ввода:

values[] = [1, 4, 5, 2, 10]
weights[] = [3, 2, 1, 2, 4]
k = 8

Ожидаемый результат:

maximumValueOfItemsInK = 20;

Алгоритм:

1) Sort values and weights by value/weight.
   values[] = [5, 10, 4, 2, 1]
   weights[] = [1, 4, 2, 2, 3]
2) currentWeight = 0; currentValue = 0;
3) FOR i = 0; currentWeight < k && i < values.length; i++ DO:
       IF k - currentWeight < weights[i] DO
           currentValue = currentValue + values[i];
           currentWeight = currentWeight + weights[i];
       ELSE
           currentValue = currentValue + values[i]*(k - currentWeight)/weights[i]
           currentWeight = currentWeight + weights[i]*(k - currentWeight)/weights[i]
       END_IF
   END_FOR
   PRINT "maximumValueOfItemsInK = " + currentValue;

Кодирование Хаффмана

Код Хаффмана - это особый тип оптимального префиксного кода, который обычно используется для сжатия данных без потерь. Он сжимает данные, очень эффективно экономя от 20% до 90% памяти, в зависимости от характеристик сжатых данных. Мы рассматриваем данные как последовательность символов. Жадный алгоритм Хаффмана использует таблицу, показывающую, как часто каждый символ (т.е. его частота) генерирует оптимальный способ представления каждого символа в виде двоичной строки. Код Хаффмана был предложен Дэвидом А. Хаффманом в 1951 году.

Предположим, у нас есть файл данных размером 100 000 символов, который мы хотим сохранить компактно. Мы предполагаем, что в этом файле всего 6 разных символов. Частота символов задается:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

У нас есть много вариантов, как представлять такой файл информации. Здесь мы рассмотрим проблему проектирования двоичного символьного кода, в котором каждый символ представлен уникальной двоичной строкой, которую мы называем кодовым словом .

Построенное дерево предоставит нам:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

Если мы используем код фиксированной длины , нам нужны три бита для представления 6 символов. Этот метод требует 300 000 бит для кодирования всего файла. Теперь вопрос в том, можем ли мы сделать лучше?

Код переменной длины может значительно превосходить код фиксированной длины, предоставляя частые символы коротких кодовых слов и нечетные символы длинными кодовыми словами. Этот код требует: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 бит для представления файла, что экономит примерно 25% памяти.

Одна вещь, которую следует помнить, мы рассматриваем здесь только коды, в которых кодовое слово не является также префиксом некоторого другого кодового слова. Они называются префиксными кодами. Для кодирования с переменной длиной мы кодируем 3-символьный файл abc как 0.101.100 = 0101100, где «.» обозначает конкатенацию.

Префиксные коды желательны, потому что они упрощают декодирование. Так как никакое кодовое слово не является префиксом для любого другого, кодовое слово, которое начинает кодированный файл, недвусмысленно. Мы можем просто определить исходное кодовое слово, перевести его обратно на исходный символ и повторить процесс декодирования в остальной части закодированного файла. Например, 001011101 анализирует однозначно как 0.0.101.1101, который декодирует до aabe . Короче говоря, все комбинации двоичных представлений уникальны. Скажем, например, если одна буква обозначена символом 110, никакая другая буква не будет обозначена 1101 или 1100. Это связано с тем, что вы можете столкнуться с путаницей в том, следует ли выбирать 110 или продолжать конкатенировать следующий бит и выбирать его.

Техника сжатия:

Эта технология работает, создавая двоичное дерево узлов. Они могут храниться в регулярном массиве, размер которого зависит от количества символов, n . Узел может быть либо листовым, либо внутренним узлом . Первоначально все узлы являются листовыми узлами, которые содержат сам символ, его частоту и, необязательно, ссылку на его дочерние узлы. В качестве условного обозначения бит «0» представляет собой левый дочерний элемент, а бит «1» представляет собой правильный ребенок. Приоритетная очередь используется для хранения узлов, которая обеспечивает узел с наименьшей частотой при выталкивании. Процесс описан ниже:

1. Создайте листовой узел для каждого символа и добавьте его в очередь приоритетов.
2. Хотя в очереди находится более одного узла:
   1. Удалите из очереди два узла с наивысшим приоритетом.
   2. Создайте новый внутренний узел с этими двумя узлами как дочерние и с частотой, равной сумме частоты двух узлов.
   3. Добавьте новый узел в очередь.
3. Остальным узлом является корневой узел, а дерево Хаффмана завершено.

Для нашего примера:

Псевдокод выглядит так:

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

Хотя заданный для линейного времени отсортированный вход, в общем случае произвольного ввода, с использованием этого алгоритма требует предварительной сортировки. Таким образом, поскольку сортировка занимает O (nlogn) время в общих случаях, оба метода имеют одинаковую сложность.

Поскольку n здесь - количество символов в алфавите, которое обычно является очень маленьким числом (по сравнению с длиной сообщения, которое должно быть закодировано), сложность времени не очень важна при выборе этого алгоритма.

Техника декомпрессии:

Процесс декомпрессии - это просто перевод текста префиксных кодов на индивидуальное значение байта, обычно путем перемещения узла дерева Хаффмана по узлу, поскольку каждый бит считывается из входного потока. Достижение листового узла обязательно завершает поиск этого конкретного байтового значения. Значение листа представляет желаемый символ. Обычно дерево Хаффмана построено с использованием статистически скорректированных данных по каждому циклу сжатия, поэтому восстановление довольно просто. В противном случае информация для восстановления дерева должна быть отправлена ​​отдельно. Псевдокод:

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

Жадный Пояснение:
Кодирование Хаффмана рассматривает появление каждого символа и сохраняет его как двоичную строку оптимальным образом. Идея состоит в том, чтобы назначать коды переменной длины для ввода входных символов, длина назначенных кодов основана на частотах соответствующих символов. Мы создаем двоичное дерево и работаем на нем снизу вверх, чтобы наименьшие два частых символа были как можно дальше от корня. Таким образом, самый частый персонаж получает наименьший код, а наименее частый персонаж получает самый большой код.

Рекомендации:

• Введение в алгоритмы - Чарльз Э. Лейзерсон, Клиффорд Штайн, Рональд Ривест и Томас Х. Кормен
• Кодирование Хаффмана - Википедия
• Дискретная математика и ее приложения - Кеннет Х. Розен

Проблема изменения

Учитывая денежную систему, можно ли предоставить количество монет и как найти минимальный набор монет, соответствующий этой сумме.

Канонические денежные системы. Для некоторой денежной системы, такой как те, которые мы используем в реальной жизни, «интуитивное» решение работает отлично. Например, если различные монеты евро и счета (за исключением центов) составляют 1 €, 2 €, 5 €, 10 €, давая самую высокую монету или счет, пока мы не достигнем суммы, и повторение этой процедуры приведет к минимальному набору монет ,

Мы можем сделать это рекурсивно с OCaml:

(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
  let rec loop given amount =
    if amount = 0 then given
    else 
      (* we find the first value smaller or equal to the remaining amount *)
      let coin = List.find ((>=) amount) money_system in
      loop (coin::given) (amount - coin)
  in loop [] amount

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

Общий случай. Как дать 99 € с монетами 10 €, 7 € и 5 €? Здесь, давая монеты в 10 €, пока мы не останемся с 9 €, очевидно, не будет решения. Хуже того, что решение может не существовать. Эта проблема на самом деле является np-hard, но приемлемые решения, связанные с жадностью и памятью, существуют. Идея состоит в том, чтобы исследовать все возможности и выбрать тот, у которого минимальное количество монет.

Чтобы дать сумму X> 0, мы выберем часть P в денежной системе, а затем решим подзапрос, соответствующий XP. Мы пробуем это для всех частей системы. Решение, если оно существует, является наименьшим путем, который привел к 0.

Здесь рекурсивная функция OCaml, соответствующая этому методу. Он возвращает None, если решение не существует.

(* option utilities *)
let optmin x y =
  match x,y with
  | None,a | a,None -> a
  | Some x, Some y-> Some (min x y)

let optsucc = function
  | Some x -> Some (x+1)
  | None -> None

(* Change-making problem*)
let change_make money_system amount =
  let rec loop n =
    let onepiece acc piece =
      match n - piece with
      | 0 -> (*problem solved with one coin*) 
             Some 1
      | x -> if x < 0 then 
               (*we don't reach 0, we discard this solution*)
               None
             else
               (*we search the smallest path different to None with the remaining pieces*) 
               optmin (optsucc (loop x)) acc
    in
    (*we call onepiece forall the pieces*)
    List.fold_left onepiece None money_system
  in loop amount

Примечание . Можно заметить, что эта процедура может вычислить несколько раз набор изменений для того же значения. На практике использование memoization во избежание повторений приводит к более быстрым (более быстрым) результатам.

Проблема выбора действия

Эта проблема

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

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

Помните, что вы не можете брать два класса одновременно. Это означает, что вы не можете брать классы 1 и 2, потому что они имеют общее время с 10.30 до 11.00. Однако вы можете взять класс 1 и 3, потому что они не имеют общего времени. Поэтому ваша задача - максимально использовать максимальное количество классов без каких-либо совпадений. Как вы можете это сделать?

Анализ

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

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

порядок сортировки будет 4 -> 1 -> 2 -> 3. Будет выполняться активность 4 -> 1 -> 3, и активность 2 будет пропущена. будет выполнено максимум 3 активности. Он работает для подобных случаев. но в некоторых случаях это не удастся. Давайте применим этот подход для случая

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

• Сортируйте активность по длительности, которая означает самую короткую деятельность. что может решить предыдущую проблему. Хотя проблема не полностью решена. Есть еще некоторые случаи, которые могут привести к отказу в решении. примените этот подход на примере ниже.

если сортировать активность по времени, порядок сортировки будет 2 -> 3 ---> 1. и если мы сначала выполняем деятельность № 2, тогда никакая другая деятельность не может быть выполнена. Но ответ будет выполнять активность 1, а затем выполнить 3. Таким образом, мы можем выполнять максимум 2 действия. Таким образом, это не может быть решением этой проблемы. Мы должны попробовать другой подход.

Решение

• Сортировка активности по окончанию времени, что означает, что сначала завершается действие, которое начинается первым. алгоритм приведен ниже

1. Сортируйте действия по времени окончания.
2. Если выполняемая деятельность не имеет общего времени с ранее выполненными действиями, выполните эту операцию.

Давайте проанализируем первый пример

Сортировка активности по времени ее окончания. Таким образом, порядок сортировки будет 1 -> 5 -> 2 -> 4 -> 3 .. ответ будет 1 -> 3, эти два действия будут выполнены. ans - это ответ. вот код sudo.

1. сортировать: деятельность
2. выполнить первую операцию из отсортированного списка видов деятельности.
3. Set: Current_activity: = первая активность
4. set: end_time: = end_time текущей активности
5. перейти к следующему действию, если оно существует, если оно не существует.
6. если start_time текущей активности <= end_time: выполните действие и перейдите к 4
7. еще: добрался до 5.

см. здесь для справки по кодированию http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/