그리디 알고리즘과 C++에서의 구현

그리디 알고리즘은 일반적으로 사용되는 알고리즘 아이디어로 많은 문제에 널리 사용됩니다. 핵심 아이디어는 장기적인 영향을 고려하지 않고 각 단계에서 결정을 내릴 때 즉각적인 최적의 솔루션만 고려하는 것입니다.

C++에서 그리디 알고리즘의 구현에는 정렬 및 데이터 처리와 같은 기본 작업이 포함되는 경우가 많습니다. 아래에서는 몇 가지 일반적인 문제에 대한 그리디 알고리즘의 아이디어와 C++에서의 구현을 소개합니다.

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. 허프만 코딩 문제

주어진 가중치 값 집합을 모든 값의 합에 대한 인코딩 길이가 되도록 서로 다른 길이의 이진 문자열로 인코딩해야 합니다. 최소화됩니다.

그리디 알고리즘의 아이디어는 먼저 가중치를 오름차순으로 정렬하고 각 단계에서 가장 작은 가중치를 가진 두 개의 노드를 선택하여 새 노드로 결합한 다음 해당 가중치를 가중치의 합으로 정의하는 것입니다. 두 노드 중. 모든 노드가 루트 노드로 결합될 때까지 이 과정을 반복합니다. 이 루트 노드에 해당하는 이진 트리는 허프만 트리입니다. 허프만 트리를 순회할 때 왼쪽으로 걷는 것은 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;
}

실제 개발 과정에서 그리디 알고리즘은 최적의 솔루션이 아닌 경우가 많지만 단순성과 효율성으로 인해 널리 사용됩니다. 위의 세 가지 일반적인 문제를 소개함으로써 독자는 탐욕 알고리즘의 아이디어와 C++에서의 구현을 더 잘 이해하고 숙달할 수 있다고 믿습니다.

위 내용은 그리디 알고리즘과 C++에서의 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!