Greedy アルゴリズムとその C++ での実装

貪欲アルゴリズムは一般的に使用されるアルゴリズムのアイデアであり、多くの問題で広く使用されています。中心的な考え方は、各ステップで意思決定を行う際に、長期的な影響を考慮せず、当面の最適なソリューションのみを考慮することです。

C では、貪欲アルゴリズムの実装には、ソートやデータ処理などの基本的な操作が含まれることがよくあります。以下では、いくつかの典型的な問題に対する貪欲アルゴリズムの考え方と C での実装を紹介します。

1. アクティビティのスケジュール設定の問題

一連のアクティビティがある場合、各アクティビティには開始時間と終了時間があり、人は一度に 1 つのアクティビティのみに参加できます。この人が最大限の数のアクティビティに参加できるようにアクティビティを手配する方法を尋ねます。

貪欲アルゴリズムの考え方は、まず各アクティビティを終了時間の昇順に並べ替え、次に最初のアクティビティから開始して、終了時間が最も早いアクティビティを最初に参加するアクティビティとして選択することです。 。次に、残りのアクティビティの中から現在のアクティビティと互換性のある終了時刻が最も早いアクティビティを選択し、次に参加するアクティビティとします。すべてのアクティビティのスケジュールが完了するまで、このプロセスを繰り返します。

次は C コードの実装です:

struct activity {
    int start;
    int end;
}

bool cmp(activity a, activity b) {
    return a.end < b.end;
}

int arrangeActivities(activity arr[], int n) {
    sort(arr, arr + n, cmp);
    int cnt = 1;
    int lastEnd = arr[0].end;
    for (int i = 1; i < n; i++) {
        if (arr[i].start >= lastEnd) {
            cnt++;
            lastEnd = arr[i].end;
        }
    }
    return cnt;
}

2. ハフマン エンコードの問題

重みのセットが与えられると、それらは等しくない長さのバイナリ文字にエンコードされる必要があります。文字列を使用して、すべての値の合計のエンコード長が最小化されるようにします。

貪欲アルゴリズムの考え方は、最初に重みを昇順に並べ替え、各ステップで最小の重みを持つ 2 つのノードを選択して新しいノードに結合し、その重みを次のように定義することです。これら 2 つのノードの重みの合計。すべてのノードがルート ノードに結合されるまで、このプロセスを繰り返します。このルートノードに対応する二分木がハフマン木です。ハフマン木をたどるとき、左に歩くことは 0 を追加することを意味し、右に歩くことは 1 を追加することを意味します。このようにして、各重みの対応するエンコードを解決できます。

次は C コードの実装です:

struct Node {
    int weight;
    int parent, leftChild, rightChild;
}

bool cmp(Node a, Node b) {
    return a.weight < b.weight;
}

void buildHuffmanTree(Node arr[], int n) {
    // 初始化所有节点
    for (int i = 0; i < n; i++) {
        arr[i].parent = -1;
        arr[i].leftChild = -1;
        arr[i].rightChild = -1;
    }

    // 构建哈夫曼树
    for (int i = n; i < 2 * n - 1; i++) {
        int minIndex1 = -1, minIndex2 = -1;
        for (int j = 0; j < i; j++) {
            if (arr[j].parent == -1) {
                if (minIndex1 == -1) {
                    minIndex1 = j;
                }
                else if (minIndex2 == -1) {
                    minIndex2 = j;
                }
                else {
                    if (arr[j].weight < arr[minIndex1].weight) {
                        minIndex2 = minIndex1;
                        minIndex1 = j;
                    }
                    else if (arr[j].weight < arr[minIndex2].weight) {
                        minIndex2 = j;
                    }
                }
            }
        }
        arr[minIndex1].parent = i;
        arr[minIndex2].parent = i;
        arr[i].leftChild = minIndex1;
        arr[i].rightChild = minIndex2;
        arr[i].weight = arr[minIndex1].weight + arr[minIndex2].weight;
    }
}

void findHuffmanCode(Node arr[], int n) {
    // 从叶节点开始遍历哈夫曼树
    for (int i = 0; i < n; i++) {
        string code = "";
        int currentNode = i;
        while (arr[currentNode].parent != -1) {
            int parent = arr[currentNode].parent;
            if (arr[parent].leftChild == currentNode) {
                code = "0" + code;
            }
            else {
                code = "1" + code;
            }
            currentNode = parent;
        }
        cout << code << endl;
    }
}

3. コインのつり銭問題の解決

コインのセットの額面と、必要なつりの金額が与えられると、この金額を構成するために必要なコインの枚数を尋ねます。

貪欲なアルゴリズムの考え方は、まず額面の降順でコインを並べ替え、次に額面が最大のコインから始めて、選択ができなくなるまでコインを取り続けることです。 、すべての金額が集まるまで、額面の次に大きいコインを使用します。

次は C コードの実装です:

bool cmp(int a, int b) {
    return a > b;
}

int minCoinNum(int coins[], int n, int amount) {
    sort(coins, coins + n, cmp);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (amount >= coins[i]) {
            cnt += amount / coins[i];
            amount -= coins[i] * (amount / coins[i]);
        }
    }
    return cnt;
}

実際の開発プロセスでは、欲張りアルゴリズムは最適なソリューションではないことがよくありますが、そのシンプルさと効率性により広く使用されています。上記の 3 つの典型的な問題の紹介を通じて、読者は貪欲なアルゴリズムとその C での実装の概念をよりよく理解し、習得できると思います。

以上がGreedy アルゴリズムとその C++ での実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。