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 %까지 메모리를 매우 효과적으로 압축합니다. 데이터는 일련의 문자로 간주됩니다. 허프만의 그리 디 알고리즘은 각 문자가 얼마나 빈번히 발생하는지 (즉 빈도)를 나타내는 표를 사용하여 각 문자를 이진 문자열로 표현하는 최적의 방법을 구축합니다. Huffman 코드는 1951 년 David A. Huffman 에 의해 제안되었습니다.

우리가 조밀하게 저장하고자하는 10 만 자의 데이터 파일이 있다고 가정합니다. 우리는 그 파일에 단지 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자를 표현하기 위해 3 비트가 필요합니다. 이 방법은 전체 파일을 코딩하는 데 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으로 코딩합니다. 여기서 "." 연결을 나타냅니다.

프리픽스 코드는 디코딩을 단순화하기 때문에 바람직합니다. 아무 코드 워드도 다른 어떤 것의 접두사가 아니기 때문에 인코딩 된 파일을 시작하는 코드 워드는 모호하지 않습니다. 단순히 초기 코드 워드를 확인하고 원래 문자로 다시 변환 한 다음 인코딩 된 파일의 나머지 부분에 대해 디코딩 프로세스를 반복 할 수 있습니다. 예를 들어, 001,011,101은 aabe로 디코딩하는 0.0.101.1101으로 고유 구문 분석합니다. 요컨대, 이원 표현의 모든 조합은 고유합니다. 예를 들어, 하나의 문자가 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

욕심 많은 설명 :
허프만 코딩은 각 문자의 발생을 살펴보고이를 최적의 방식으로 이진 문자열로 저장합니다. 아이디어는 가변 길이 부호를 입력 문자에 할당하는 것이며, 할당 된 코드의 길이는 해당 문자의 빈도를 기반으로합니다. 우리는 이진 트리를 생성하고 상향식 방식으로 작동시켜 최소 두 개의 빈번한 문자가 가능한 한 루트에서 멀어 지도록합니다. 이렇게하면 가장 빈번한 문자가 가장 작은 코드를 얻고 가장 적은 문자가 가장 큰 코드를 얻습니다.

참고 문헌 :

• 알고리즘 소개 - Charles E. Leiserson, Clifford Stein, Ronald Rivest, Thomas H. Cormen
• 허프만 코딩 - 위키 백과
• 이산 수학과 그 응용 - Kenneth H. Rosen

변화하는 문제

돈 시스템이 주어지면 일정량의 동전을주고이 금액에 해당하는 최소 동전 세트를 찾는 것이 가능합니까?

표준 화폐 시스템. 우리가 실제 생활에서 사용하는 돈 시스템처럼 "직관적 인"솔루션이 완벽하게 작동합니다. 예를 들어, 다른 유로화와 지폐 (센트 제외)가 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

이러한 시스템은 변경이 용이하도록 만들어졌습니다. 문제는 임의의 화폐 시스템에 있어서는 어려워진다.

일반적인 경우. 10 €, 7 € 및 5 €의 동전으로 99 €를주는 방법? 우리가 9 €로 남겨질 때까지 여기에서, 10 €의 동전을주는 것은 명백하게 아무 해결책도 이끌지 않는다. 그 이상의 해결책은 존재하지 않을 수도 있습니다. 이 문제는 사실 np-hard이지만 탐욕 과 메모 가 혼합 된 수용 가능한 솔루션이 존재합니다. 아이디어는 모든 가능성을 탐구하고 동전의 최소 숫자로 하나를 선택하는 것입니다.

X> 0의 양을주기 위해 돈 시스템에서 P를 선택하고 XP에 해당하는 하위 문제를 푸십시오. 시스템의 모든 부분에 대해이 작업을 시도합니다. 해결책이 존재한다면, 0이되는 가장 작은 경로입니다.

다음은이 메서드에 해당하는 OCaml 재귀 함수입니다. 솔루션이 없으면 없음을 반환합니다.

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

참고 :이 절차는 동일한 값에 대해 변경 집합을 여러 번 계산할 수 있습니다. 실제로 이러한 반복을 피하기 위해 메모를 사용하면 더 빠른 (빠른 방식으로) 결과를 얻을 수 있습니다.

활동 선택 문제

문제

당신은해야 할 일들이 있습니다 (활동). 각 활동에는 시작 시간과 종료 시간이 있습니다. 한 번에 두 가지 이상의 활동을 수행 할 수 없습니다. 당신의 임무는 최대 활동 횟수를 수행하는 방법을 찾는 것입니다.

예를 들어 선택할 클래스가 있다고 가정합니다.

동시에 두 과목을들을 수는 없습니다. 즉, 수업 1과 수업 2를들을 수 없다는 의미입니다. 왜냐하면 수업 시간은 오전 10시 30 분에서 밤 11 시까 지입니다. 그러나 수업 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이며이 두 가지 활동이 수행됩니다. 대답은 그 대답입니다. 여기에 sudo 코드가있다.

1. 정렬 : 활동
2. 정렬 된 활동 목록에서 첫 번째 활동을 수행하십시오.
3. 집합 : Current_activity : = 첫 번째 활동
4. set : end_time : = 현재 활동의 end_time
5. 존재하지 않으면 다음 활동으로 이동하고, 존재하지 않으면 종료하십시오.
6. 현재 활동의 시작 시간이 <= end_time 인 경우 : 활동을 수행하고 4로 이동하십시오.
7. else : 5에 도달했습니다.

코딩 도움말은 여기를 참고하십시오. http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/