algorithm
Chciwe Algorytmy

Uwagi

Ciągły problem z plecakiem

Biorąc pod uwagę przedmioty jako (value, weight) , musimy je umieścić w plecaku (pojemniku) o pojemności k . Uwaga! Możemy rozkładać przedmioty, aby zmaksymalizować wartość!

Przykładowe dane wejściowe:

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

Oczekiwany wynik:

maximumValueOfItemsInK = 20;

Algorytm:

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;

Kodowanie Huffmana

Kod Huffmana jest szczególnym typem optymalnego kodu prefiksu, który jest powszechnie używany do bezstratnej kompresji danych. Bardzo skutecznie kompresuje dane, oszczędzając od 20% do 90% pamięci, w zależności od właściwości kompresowanych danych. Dane traktujemy jako ciąg znaków. Chciwy algorytm Huffmana korzysta z tabeli podającej częstotliwość występowania każdego znaku (tj. Jego częstotliwości), aby stworzyć optymalny sposób reprezentowania każdego znaku jako ciągu binarnego. Kod Huffmana zaproponował David A. Huffman w 1951 r.

Załóżmy, że mamy plik danych o długości 100 000 znaków, który chcemy przechowywać w kompaktowy sposób. Zakładamy, że w tym pliku jest tylko 6 różnych znaków. Częstotliwość znaków podaje:

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

Mamy wiele opcji reprezentowania takiego pliku informacji. Rozważamy tutaj problem projektowania binarnego kodu znaków, w którym każdy znak jest reprezentowany przez unikalny ciąg binarny, który nazywamy słowem kodowym .

Zbudowane drzewo zapewni nam:

+------------------------+-----+-----+-----+-----+-----+-----+
|        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|
+------------------------+-----+-----+-----+-----+-----+-----+

Jeśli użyjemy kodu o stałej długości , potrzebujemy trzech bitów do przedstawienia 6 znaków. Ta metoda wymaga 300 000 bitów do zakodowania całego pliku. Teraz pytanie brzmi: czy możemy zrobić lepiej?

Kod o zmiennej długości może być znacznie lepszy niż kod o stałej długości, ponieważ często wpisuje krótkie słowa kodowe, a rzadko długie słowa kodowe. Ten kod wymaga: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bitów do przedstawienia pliku, co oszczędza około 25% pamięci.

Należy pamiętać, że rozważamy tutaj tylko kody, w których żadne słowo kodowe nie jest również przedrostkiem jakiegoś innego słowa kodowego. Są to tak zwane kody prefiksów. W celu kodowania o zmiennej długości kodujemy 3-znakowy plik abc jako 0.101.100 = 0101100, gdzie „.” oznacza konkatenację.

Kody prefiksów są pożądane, ponieważ upraszczają dekodowanie. Ponieważ żadne słowo kodowe nie jest przedrostkiem żadnego innego, słowo kodowe, które rozpoczyna kodowany plik, jest jednoznaczne. Możemy po prostu zidentyfikować początkowe słowo kodowe, przetłumaczyć je z powrotem na oryginalny znak i powtórzyć proces dekodowania na pozostałej części zakodowanego pliku. Na przykład 001011101 analizuje unikatowo jako 0.0.101.1101, który dekoduje do aabe . Krótko mówiąc, wszystkie kombinacje reprezentacji binarnych są unikalne. Powiedzmy na przykład, jeśli jedna litera jest oznaczona przez 110, żadna inna litera nie będzie oznaczona przez 1101 lub 1100. Jest tak, ponieważ możesz napotkać zamieszanie, czy wybrać 110, czy kontynuować konkatenację następnego bitu i wybierz tę.

Technika kompresji:

Technika polega na utworzeniu binarnego drzewa węzłów. Mogą być przechowywane w regularnej tablicy, której rozmiar zależy od liczby symboli, n . Węzeł może być węzłem liścia lub węzłem wewnętrznym . Początkowo wszystkie węzły są węzłami liści, które zawierają sam symbol, jego częstotliwość i opcjonalnie łącze do jego węzłów potomnych. Tradycyjnie bit „0” reprezentuje lewe dziecko, a bit „1” reprezentuje prawe dziecko. Kolejka priorytetowa jest używana do przechowywania węzłów, co zapewnia węzełowi najniższą częstotliwość, gdy jest otwierany. Proces opisano poniżej:

1. Utwórz węzeł liścia dla każdego symbolu i dodaj go do kolejki priorytetowej.
2. Podczas gdy w kolejce jest więcej niż jeden węzeł:
   1. Usuń dwa kolejki o najwyższym priorytecie z kolejki.
   2. Utwórz nowy węzeł wewnętrzny z tymi dwoma węzłami jako dziećmi i z częstotliwością równą sumie częstotliwości dwóch węzłów.
   3. Dodaj nowy węzeł do kolejki.
3. Pozostały węzeł jest węzłem głównym, a drzewo Huffmana jest kompletne.

W naszym przykładzie:

Pseudo-kod wygląda następująco:

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

Chociaż dane wejściowe posortowane w czasie liniowym, w ogólnych przypadkach arbitralnych danych wejściowych, użycie tego algorytmu wymaga wstępnego sortowania. Zatem, ponieważ sortowanie zajmuje czas O (nlogn) w ogólnych przypadkach, obie metody mają tę samą złożoność.

Ponieważ n oznacza liczbę symboli w alfabecie, która zazwyczaj jest bardzo małą liczbą (w porównaniu z długością zakodowanej wiadomości), złożoność czasu nie jest bardzo ważna przy wyborze tego algorytmu.

Technika dekompresyjna:

Proces dekompresji polega po prostu na przełożeniu strumienia kodów prefiksów na poszczególne wartości bajtów, zwykle przez przemierzanie drzewa Huffmana węzeł po węźle, gdy każdy bit jest odczytywany ze strumienia wejściowego. Dotarcie do węzła liścia koniecznie kończy wyszukiwanie tej konkretnej wartości bajtu. Wartość liścia reprezentuje pożądany znak. Zwykle drzewo Huffmana jest konstruowane przy użyciu danych statystycznie dostosowanych dla każdego cyklu kompresji, dlatego rekonstrukcja jest dość prosta. W przeciwnym razie informacje potrzebne do odtworzenia drzewa należy wysłać osobno. Pseudo-kod:

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

Chciwy Objaśnienie:
Kodowanie Huffmana sprawdza występowanie każdego znaku i przechowuje go jako ciąg binarny w optymalny sposób. Pomysł polega na przypisaniu kodów o zmiennej długości do wprowadzania znaków wejściowych, długość przypisanych kodów zależy od częstotliwości odpowiednich znaków. Tworzymy drzewo binarne i działamy na nim w sposób oddolny, aby co najmniej dwie częste postacie znajdowały się jak najdalej od katalogu głównego. W ten sposób najczęstszy znak otrzymuje najmniejszy kod, a najmniejszy znak otrzymuje największy kod.

Bibliografia:

• Wprowadzenie do algorytmów - Charles E. Leiserson, Clifford Stein, Ronald Rivest i Thomas H. Cormen
• Kodowanie Huffmana - Wikipedia
• Matematyka dyskretna i jej zastosowania - Kenneth H. Rosen

Problem z wprowadzaniem zmian

Biorąc pod uwagę system pieniężny, czy można podać ilość monet i jak znaleźć minimalny zestaw monet odpowiadający tej ilości.

Kanoniczne systemy pieniężne. W przypadku niektórych systemów pieniężnych, takich jak te, których używamy w prawdziwym życiu, „intuicyjne” rozwiązanie działa idealnie. Na przykład, jeśli różne monety i rachunki euro (z wyłączeniem centów) wynoszą 1 €, 2 €, 5 €, 10 €, daje najwyższą monetę lub rachunek, dopóki nie osiągniemy kwoty i powtórzenie tej procedury doprowadzi do minimalnego zestawu monet .

Możemy to zrobić rekurencyjnie za pomocą 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

Systemy te są wykonane tak, aby dokonywanie zmian było łatwe. Problem staje się trudniejszy, jeśli chodzi o arbitralny system pieniężny.

Ogólna sprawa Jak dać 99 € za monety 10 €, 7 € i 5 €? Tutaj dawanie monet o wartości 10 €, dopóki nie zostanie nam 9 €, oczywiście nie prowadzi do rozwiązania. Co gorsza, rozwiązanie może nie istnieć. Ten problem jest w rzeczywistości trudny, ale istnieją akceptowalne rozwiązania łączące chciwość i zapamiętywanie . Chodzi o zbadanie wszystkich możliwości i wybranie tej z minimalną liczbą monet.

Aby podać kwotę X> 0, wybieramy sztukę P w systemie pieniężnym, a następnie rozwiązujemy podproblem odpowiadający XP. Próbujemy tego dla wszystkich elementów systemu. Rozwiązaniem, jeśli istnieje, jest najmniejsza ścieżka prowadząca do 0.

Tutaj funkcja rekurencyjna OCaml odpowiadająca tej metodzie. Zwraca Brak, jeśli nie ma rozwiązania.

(* 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

Uwaga : Możemy zauważyć, że ta procedura może obliczyć kilka razy zmianę ustawioną dla tej samej wartości. W praktyce stosowanie zapamiętywania w celu uniknięcia tych powtórzeń prowadzi do szybszych (o wiele szybszych) wyników.

Problem wyboru aktywności

Problem

Masz zestaw rzeczy do zrobienia (działania). Każde działanie ma czas rozpoczęcia i czas zakończenia. Nie wolno wykonywać więcej niż jednego działania na raz. Twoim zadaniem jest znalezienie sposobu na wykonanie maksymalnej liczby czynności.

Załóżmy na przykład, że masz wybór klas do wyboru.

Pamiętaj, że nie możesz brać udziału w dwóch zajęciach jednocześnie. Oznacza to, że nie możesz wziąć klasy 1 i 2, ponieważ dzielą one wspólny czas od 10.30 do 11.00. Możesz jednak wziąć klasę 1 i 3, ponieważ nie dzielą wspólnego czasu. Twoim zadaniem jest więc zajęcie jak największej liczby klas bez nakładania się. Jak możesz to robić?

Analiza

Zastanówmy się nad rozwiązaniem przez chciwe podejście. Po pierwsze, losowo wybraliśmy jakieś podejście i sprawdź, czy zadziała, czy nie.

• posortuj aktywność według czasu rozpoczęcia , co oznacza, która aktywność rozpocznie się jako pierwsza, zajmiemy się nią jako pierwsza. następnie bierz od ostatniej do posortowanej listy i sprawdź, czy będzie przecinać się z poprzednio podjętą aktywnością, czy nie. Jeśli bieżąca aktywność nie krzyżuje się z poprzednio podjętą aktywnością, wykonamy tę czynność, w przeciwnym razie nie wykonamy. takie podejście zadziała w niektórych przypadkach

kolejność sortowania będzie wynosić 4 -> 1 -> 2 -> 3. Działanie 4 -> 1 -> 3 zostanie wykonane, a działanie 2 zostanie pominięte. zostaną wykonane maksymalnie 3 czynności. Działa w tego typu przypadkach. ale w niektórych przypadkach zawiedzie. Zastosujmy to podejście do sprawy

Kolejność sortowania będzie wynosić 4 -> 1 -> 2 -> 3 i zostanie wykonane tylko działanie 4, ale odpowiedzią może być działanie 1 -> 3 lub 2 -> 3 zostaną wykonane. Dlatego nasze podejście nie będzie działać w powyższym przypadku. Wypróbujmy inne podejście

• Posortuj aktywność według czasu, co oznacza, że najpierw wykonaj najkrótszą aktywność. które mogą rozwiązać poprzedni problem. Chociaż problem nie został całkowicie rozwiązany. Nadal istnieją przypadki, w których rozwiązanie może się nie powieść. zastosuj to podejście do poniższej sprawy.

jeśli posortujemy aktywność według czasu, kolejność sortowania będzie wynosić 2 -> 3 ---> 1. a jeśli najpierw wykonamy czynność nr 2, wówczas nie będzie można wykonać żadnej innej czynności. Ale odpowiedzią będzie wykonanie czynności 1, a następnie wykonanie 3. Możemy więc wykonać maksymalnie 2 czynności, więc nie może to być rozwiązanie tego problemu. Powinniśmy spróbować innego podejścia.

Rozwiązanie

• Posortuj działanie według czasu zakończenia, co oznacza, że działanie kończy się jako pierwsze. algorytm podano poniżej

1. Posortuj działania według czasu zakończenia.
2. Jeśli działanie, które ma zostać wykonane, nie dzieli wspólnego czasu z działaniami, które wcześniej wykonano, wykonaj działanie.

Przeanalizujmy pierwszy przykład

posortuj działanie według czasów zakończenia, więc kolejność sortowania będzie wynosić 1 -> 5 -> 2 -> 4 -> 3 .. odpowiedź to 1 -> 3 te dwa działania zostaną wykonane. i to jest odpowiedź. oto kod sudo.

1. sortuj: działania
2. wykonaj pierwszą czynność z posortowanej listy czynności.
3. Zestaw: Current_activity: = pierwsza aktywność
4. set: end_time: = end_time bieżącej aktywności
5. przejdź do następnego działania, jeśli istnieje, jeśli nie istnieje, zakończ.
6. jeśli czas_początkowy bieżącej aktywności <= czas_końcowy: wykonaj działanie i przejdź do 4
7. else: dotarł do 5.

zobacz tutaj pomoc dotyczącą kodowania http://www.geeksforgeeks.org/greedy-alameterms-set-1-activity-selection-problem/