How to use greedy algorithm in C++

How to use the greedy algorithm in C

The greedy algorithm is an algorithm based on the principle of greedy selection. It makes the best decision at every step. selection, hoping to eventually obtain the global optimal solution. In C, we can use greedy algorithms to solve many practical problems. The following will introduce how to use the greedy algorithm in C and give specific code examples.

1. The basic principle of the greedy algorithm
The greedy algorithm is a heuristic algorithm. Its basic principle is to select the currently optimal solution each time and iterate successively until the global optimal is obtained. untie. The greedy algorithm has the following characteristics:
1. It is not guaranteed to obtain the optimal solution, but it can often obtain an approximately optimal solution;
2. It is usually more efficient than other algorithms such as dynamic programming;
3. It can solve some problems Special types of problems, such as activity selection problems, knapsack problems, etc.

2. Application of Greedy Algorithm
Greedy algorithm can be applied to many fields. Common problems are:
1. Activity selection problem: Assume there are n activities, each activity has an Start time and end time, how to arrange activities so that as many activities as possible can be carried out?
2. Backpack problem: Given the capacity of a backpack and a number of items, each item has its own weight and value. How to choose items to put into the backpack so that the total value of the items in the backpack is maximized?
3. Interval coverage problem: Given some closed intervals, select as few intervals as possible to cover the entire target interval.

3. Implementation of Greedy Algorithm
The following takes the activity selection problem as an example to explain in detail how to use the greedy algorithm in C.

Problem description:
Suppose there are n activities, each activity has a start time and end time. It is required to select as many activities as possible so that these activities do not conflict, that is, the time periods of any two activities cannot overlap.

Problem-solving ideas:
1. Sort the activities according to the end time, giving priority to activities with an early end time;
2. Select the first activity initially, and then select the next end time and Activities that do not conflict with the end time of the previous activity.

Code implementation:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//定义活动结构体
struct activity{
    int start;
    int end;
};

//比较函数，按照结束时间从小到大排序
bool compare(activity a1, activity a2){
    return a1.end < a2.end;
}

//贪心算法求解活动选择问题
int greedyActivitySelector(vector<activity>& activities){
    //按照结束时间从小到大排序
    sort(activities.begin(), activities.end(), compare);
    
    int result = 1;  //记录最终选择的活动数量
    int preEnd = activities[0].end;  //记录前一个活动的结束时间
    
    for(int i = 1; i < activities.size(); i++){
        if(activities[i].start >= preEnd){
            result++;
            preEnd = activities[i].end;
        }
    }
    
    return result;
}

int main(){
    vector<activity> activities;
    int n;
    cout << "请输入活动个数：" << endl;
    cin >> n;
    
    cout << "请输入每个活动的开始时间和结束时间：" << endl;
    for(int i = 0; i < n; i++){
        activity act;
        cin >> act.start >> act.end;
        activities.push_back(act);
    }
    
    int result = greedyActivitySelector(activities);
    cout << "可以选择的活动数量为：" << result << endl;
    
    return 0;
}

The above code implements the greedy algorithm for the activity selection problem. The program first sorts the input activities from small to large by end time. Then starting from the first activity, select the next activity that does not conflict with the previous activity, and finally get the number of activities that can be selected.

4. Summary
The greedy algorithm is a simple and efficient algorithm that is often used to solve practical problems. We can easily use C's containers and algorithm libraries to implement greedy algorithms, such as vector containers, sorting algorithms, etc. However, it should be noted that the greedy algorithm is not suitable for all problems, and an appropriate algorithm needs to be selected according to the characteristics of the specific problem.

The above is the detailed content of How to use greedy algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!