Greedy algorithm and its implementation in C++

The greedy algorithm is a commonly used algorithm idea and is widely used in many problems. The core idea is to only consider the immediate optimal solution when making a decision at each step, without considering the long-term impact.

In C, the implementation of greedy algorithms often involves basic operations such as sorting and data processing. Below, we will introduce the idea of ​​greedy algorithm and its implementation in C for several typical problems.

1. Activity Scheduling Problem

Given a set of activities, each activity has its start time and end time, and a person can only participate in one activity at a time. Ask how to arrange activities to ensure that this person participates in the maximum number of activities.

The idea of ​​the greedy algorithm is to first sort each activity in ascending order by the end time, and then starting from the first activity, select the activity with the earliest end time as the first activity to participate. Then, select the activity with the earliest end time that is compatible with the current activity from the remaining activities and make it the next activity to participate in. Repeat this process until all activities have been scheduled.

The following is the C code implementation:

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. Huffman encoding problem

Given a set of weights, they are required to be encoded into binary characters of unequal lengths string, so that the encoding length of the sum of all values ​​is minimized.

The idea of ​​​​the greedy algorithm is to first sort the weights in ascending order, select the two nodes with the smallest weights in each step to combine into a new node, and define its weight as the weight of these two nodes. Sum. Repeat this process until all nodes are combined into a root node. The binary tree corresponding to this root node is the Huffman tree. When traversing the Huffman tree, walking to the left means adding 0, and walking to the right means adding 1, so that the corresponding encoding of each weight can be solved.

The following is the C code implementation:

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. Solving the coin change problem

Given the face value of a set of coins and the amount of change to be made, ask the minimum required How many coins are needed to make up this amount.

The idea of ​​the greedy algorithm is to first sort the coins in descending order by face value, then start with the coin with the largest face value, continue to take the coin until no more choices can be made, and then use the coin with the next largest face value until all the amount is collected. .

The following is the C code implementation:

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;
}

In the actual development process, the greedy algorithm is often not the optimal solution, but its simplicity and efficiency make it widely used. Through the introduction of the above three typical problems, I believe readers can better understand and master the idea of ​​greedy algorithm and its implementation in C.

The above is the detailed content of Greedy algorithm and its implementation in C++. For more information, please follow other related articles on the PHP Chinese website!