I saw high-quality classroom works on station b. I analyzed them with my own understanding to help you better understand them

Of course, we still need to know what is greedy algorithm:

1. Greedy algorithm means that when solving a problem, it always makes the best choice, that is, it does not consider the overall optimization. What the algorithm makes is the local optimal solution in a sense (but not the overall optimal solution for all problems)

From the problems solved by greedy algorithm, we can see that this kind of problems generally have two important properties - greedy selection property and optimal substructure property;

There is no key discussion here. Let's look at the question directly:

(1) Loading watermelon, a car can load 50 kilograms of watermelon, each watermelon is equally delicious, but the weight is different. It is required to load the most. How many can you load?

#include <stdio.h>
#include <algorithm>
using namespace std;
int main(void)
{
	int data[] = {8，9，4，3，2，13，11};
	int max = 50;
	int count = sizeof(data) / sizeof(data[0]);//Calculate a total of seven watermelons
	sort(data,data+count);//Use the sort function to sort the array from small to large (ascending order)
	int tmp = 0;
	int n = 0;
	for (int i = 0; i < count; i++)
	{
		tmp += data[i];//Weight of watermelon
		if(tmp>max)
		{
			break;
		}
		n++;
	}
	printf("%d\n",n);
	return 0;
}

The above is solved by greedy algorithm, and some knowledge points are added:

The 1.sort function is included in the c++ standard library whose header file is #include<algorithm>. The sorting method in the standard library can be used to sort the data, sort (array first, array last, parameters).

2. The template of sort function has three parameters:

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
(1) The first parameter first: is the starting address of the array to be sorted.

(2) The second parameter, last: is the end address (the address of the last data after the last data)

(3) The third parameter comp is the sorting method: it can be in ascending or descending order. If the third parameter is not written, the default sorting method is to sort from small to large.

 #include<iostream>
 #include<algorithm>
 using namespace std;
 bool cmp(int a, int b);
 main() {
    　　//The third parameter of sort function is defined by itself, and the implementation is from large to small
    　　int a[] = { 45,12,34,77,90,11,2,4,5,55 };
    　　sort(a, a + 10, cmp);
     　for (int i = 0; i < 10; i++)
         　cout << a[i] << ends;
    
}
//Custom function
bool cmp(int a, int b) {
    　　return a > b;
}

(2) Description of change change problem:
There are 50, 20, 10, 5, 1, 0.5, 0.1 and other denominations of change. The customer spent n yuan on shopping. After paying (n / 100 + 1) * 100 yuan (including one decimal place at most), how should the cashier change to minimize the amount of money recovered.

#include <iostream>
using namespace std;
double MONEY_UNIT[7] = {50, 20, 10, 5, 1, 0.5, 0.1};    //All denominations of money

int main()
{
    double consumeMoney;                            //Amount consumed
    cin >> consumeMoney;
    double realGiveMoney;                           //Actual money
    realGiveMoney = (int)(consumeMoney / 100 + 1) * 100;//The actual amount of money given is calculated by automatically rounding off the decimal places of int
    double shouldRevMoney;                          //Change you should get back
    shouldRevMoney = realGiveMoney - consumeMoney;
    //Implementation of greedy algorithm -- local optimal solution
    int revMoneyAmount = 0;
    for (int i = 0; i < 7; i ++) {
        if (MONEY_UNIT[i] <= shouldRevMoney) {
            shouldRevMoney -= MONEY_UNIT[i];
            i--;                                        //Continue to test whether the money of this denomination meets the requirements
            revMoneyAmount++;                           //The number of change pieces recovered plus 1
        }
        if (!shouldRevMoney) {
            break;
        }
    }
    cout << "The minimum number of change recovered is:";
    cout << revMoneyAmount << endl;
    return 0;
}

​

In this problem, once a greedy choice is made (the currency with the largest possible face value is selected), it can not be changed, which means that the choice can not be reversed, which is different from backtracking.

(3) Flower planting problem description:

There is a square flower bed. In order to plant flowers, the land where flowers have been planted is 1, and each kind is 0. Flowers can only be planted on 0, and there can be no flowers nearby. Otherwise, they can not be planted. Ask flower bed place [] = {1,0,1,0,1,0,1,0,1}; Can it be replanted?

#include <stdio.h>
bool canPlaceFlowers(int* place, int placeSize,int n)
{
    int i = 0;
    if (n == 0)
    {
        return 0;
    }
    int count = 0;
    while (i < placeSize)
    {
        if (place[i]==1)
        {
            i += 2;
        }
        else if (i > 0 && place[i - 1] == 1)
        {
            i += 1;
        }
        else if(i+1 < placeSize && place[i+1]==1)
        {
            i += 3;
        }
        else {
            count++;
            i += 2;
            if (count == n)
            {
                return true;
            }
        }

    }
    return false;
}
int main(void)
{
    int place[] = {1,0,1,0,1,0,1,0,1,0,0,1,0,1};
    if (canPlaceFlowers(place, sizeof(place) / sizeof(place[0]), 3))
    {
        printf("Can plant!\n");
    }
    else
    {
        printf("No planting!\n");
    }
    return 0;
}//The final output is no planting

That's all for the greedy algorithm. Please give me some advice if you don't understand it correctly

PS: Tools: vs2022