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％のメモリを非常に効果的に圧縮します。データは一連の文字とみなされます。ハフマンの欲張りアルゴリズムは、各文字がどのくらいの頻度で出現するか（すなわちその頻度）を示す表を使用して、各文字をバイナリ文字列として表現する最適な方法を構築します。ハフマンコードはDavid A. Huffmanによって1951年に提案されました。

コンパクトに保管したい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％が節約されます。

覚えておくべき1つのことは、ここではコードワードが他のコードワードのプレフィックスでもないコードのみを考える。これらはプレフィックスコードと呼ばれます。可変長コーディングでは、3文字のファイルabcを0.101.100 = 0101100としてコーディングします。 "。"連結を示す。

プレフィックスコードは、復号を単純化するので望ましい。コードワードは他のコードワードの接頭語ではないので、コード化されたファイルを開始するコードワードは明確である。最初のコードワードを特定し、元の文字に変換し、残りのエンコードされたファイルに対してデコード処理を繰り返すだけです。たとえば、001011101は、0.0.101.1101として一意に解析します 。これは、 aabeにデコードされます 。つまり、バイナリ表現のすべての組み合わせは一意です。たとえば、1つの文字が110で示されている場合、他の文字は1101または1100で表されません。これは、110を選択するか、次のビットを連結して継続するかを混乱させる可能性があるためです。

圧縮技術：

この技術は、ノードのバイナリツリーを作成することによって機能します。これらは規則的な配列で格納することができ、そのサイズはシンボルの数nに依存します。ノードはリーフノードでも内部ノードでもよい 。最初はすべてのノードがリーフノードであり、シンボル自体、その頻度、およびオプションでその子ノードへのリンクを含みます。慣例として、ビット「0」は左の子を表し、ビット「1」は右の子を表す。 優先度キューは、ノードを格納するために使用され、ポップ時にノードの周波数が最も低くなります。このプロセスを以下に説明します。

1. 各シンボルのリーフノードを作成し、プライオリティキューに追加します。
2. キューには複数のノードが存在しますが、
   1. 最高優先度の2つのノードをキューから削除します。
   2. これらの2つのノードを子として、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

貪欲な説明：
ハフマン符号化は、各文字の出現を調べ、最適な方法でバイナリ文字列として格納します。その考え方は、可変長コードを入力文字に割り当て、割り当てられたコードの長さは対応する文字の頻度に基づいています。バイナリツリーを作成し、ボトムアップ方式で動作させることで、少なくとも2つの頻繁な文字がルートから可能な限り離れているようにします。このようにして、最も頻繁に登場するキャラクタは最小のコードを取得し、最も頻度の低いキャラクタは最大のコードを取得します。

参考文献：

• アルゴリズムの紹介 - Charles E. Leiserson、Clifford Stein、Ronald Rivest、Thomas H. Cormen
• ハフマンコーディング - ウィキペディア
• 離散数学とその応用 - ケネス・ローゼン

変更の問題

マネーシステムが与えられれば、ある量のコインを与えることが可能であり、この量に対応するコインの最小セットを見つける方法は可能である。

標準的なマネーシステム。現実の生活の中で使用されているような一部のマネーシステムでは、「直感的な」ソリューションが完璧に機能します。たとえば、異なるユーロ硬貨と紙幣（セントを除く）が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ユーロに与える方法は？ここでは、10ユーロのコインを9ユーロにするまで、明らかに解決策はありません。それよりも悪い解決法は存在しないかもしれません。この問題は実際にはnp-hardですが、 貪欲とメモを混在させた許容可能なソリューションが存在します。アイデアはすべての可能性を探求し、最小限の数のコインで1つを選ぶことです。

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

注 ：この手順では、同じ値の変更セットの何倍かを計算することができます。実際には、これらの繰り返しを避けるためにメモを使用すると、より速く（途中で速く）結果につながります。

アクティビティ選択問題

問題

あなたはするべきことのセットを持っています（アクティビティ）。各アクティビティには開始時間と終了時間があります。一度に複数のアクティビティを実行することはできません。あなたの仕事は、最大数の活動を実行する方法を見つけることです。

たとえば、選択するクラスが選択されているとします。

同時に2つのクラスを受講することはできません。つまり、クラス1と2は共通の時間を共有しているため、午前10時半から午後11時までは授業を受講できません。ただし、クラス1と3は共通の時間を共有しないため、クラス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です。この2つのアクティビティーが実行されます。それは答えです。ここにはsudoのコードがあります。

1. ソート：アクティビティ
2. ソートされたアクティビティのリストから最初のアクティビティを実行します。
3. 設定：Current_activity：=最初のアクティビティ
4. set：end_time：=現在のアクティビティのend_time
5. 存在しない場合は次のアクティビティに移動し、存在しない場合は終了します。
6. 現在のアクティビティのstart_time <= end_timeの場合：アクティビティを実行して4に進みます
7. else：5になった。

コーディングヘルプについてはこちらを参照してください。http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/