Article directory
- 1. Overview of Greedy Algorithm
- 2. Event arrangement issues
-
- 2.1 Problem overview
- 2.2 Code writing
- 3. Backpack Problem
-
- 3.1 Problem description
- 3.2 Code writing
1. Overview of greedy algorithm
?1. Definition of greedy algorithm: Greedy algorithm means that when solving a problem, always make the best choice at present. In other words, we do not consider the overall optimal solution, but only make a local optimal solution in a certain sense.
?2. Note: The greedy algorithm can quickly obtain the overall optimal solution for some problems. For some problems, although the overall optimal solution cannot be obtained, an approximately optimal solution can be obtained.
?3. To solve the problem using the greedy algorithm, the following conditions must be met:
- Greedy selection property: The greedy selection property means that the overall optimal solution to the problem can be obtained through a series of local optimal choices, that is, through greedy selection.
- Optimal substructure property: The optimal solution of a problem contains the optimal solutions of its sub-problems.
?4. The difference between greedy algorithm and dynamic programming:
- Same: Greedy algorithm and dynamic programming algorithm both require the problem to have optimal substructure properties.
- Difference: Dynamic programming algorithms usually solve each sub-problem in a bottom-up manner; greedy algorithms usually solve each sub-problem in a top-down manner, and each time a greedy choice is made, the problem is simplified into smaller sub-problems.
?5. The general steps of greedy algorithm to solve problems are:
- Build a mathematical model to describe the problem.
- Divide the problem to be solved into several sub-problems.
- Solve each sub-problem and obtain the local optimal solution of the sub-problem.
- Synthesize the local optimal solution of the sub-problem into a solution to the original problem.
2. Event arrangement issues
2.1 Problem Overview
?1. Yes
n
n
n activities requiring use of the same classroom on the same day:
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1?,a2?,…,an?. The classroom can only be used by one activity at a time. each activity
a
i
a_i
ai? has a start time
s
i
s_i
si? and end time
f
i
f_i
Fi?. Once selected, the activity
a
i
a_i
ai? occupies the half-open time interval
[
s
i
,
f
i
)
[s_i,f_i)
[si?,fi?). if
[
s
i
,
f
i
)
[s_i,f_i)
[si?,fi?) and
[
s
j
,
f
j
)
[s_j,f_j)
[sj?,fj?) do not overlap each other,
a
i
a_i
ai? and
a
j
a_j
aj? Two activities can be scheduled for this day. The problem is to arrange these activities so that as many as possible can be held without conflict.
?2. It can be proved by mathematical induction that our greedy strategy should be to select the activity with the earliest end time each time. It is also intuitively easy to understand that selecting compatible activities in this way leaves as much time as possible for unscheduled activities. This is also the reason why activities are sorted in monotonically increasing order by end time.
2.2 Code writing
?1. Code that doesn’t require us to sort:
#include <bits/stdc + + .h>
using namespace std;
void activity_select(int n, int s[], int f[], int selected[]){<!-- -->
int j = 0; // j records the most recently joined activity
selected[0] = 1; //Select activity 0 first
for (int i = 1; i < n; i + + )
{<!-- -->
if (s[i] >= f[j])
{<!-- --> // If activity i is compatible with activity j, select activity i
selected[i] = 1;
j = i;
} else
{<!-- -->
selected[i] = 0;
}
}
}
int main(){<!-- -->
cout << "Please enter the number of activities:";
int n;
cin >> n;
int s[n], f[n]; // s[i], f[i] stores the start and end time of activity i
int selected[n]; // If activity i is selected, selected[i] is set to 1, otherwise it is set to 0
cout << "Please enter the start and end time of the activity (enter in ascending order of end time):" << endl;
for (int i = 0; i < n; i + + )
{<!-- -->
cin >> s[i] >> f[i];
}
activity_select(n, s, f, selected);
cout << "The following activities are selected:" << endl;
for (int i = 0; i < n; i + + )
{<!-- -->
if (selected[i] == 1)
{<!-- -->
cout << i + 1 << " "; // Add 1 when outputting the activity number, because users are numbered starting from 1
}
}
return 0;
}
?2. The code we need to sort:
#include<bits/stdc + + .h>
#include<iostream>
using namespace std;
struct activity //Activity structure
{<!-- -->
int start;
int end;
};
bool cmp(activity a, activity b) //The cmp parameter is the sorting criterion of the sort function, which is set to sort from small to large according to the end time of the activity
{<!-- -->
return a.end<b.end;
}
void activity_select(int n,int selected[],activity act[])
{<!-- -->
int i=1;
selected[1]=1;
for(int j=2;j<=n;j + + ) //Start traversing from the activity with the second to last end time
{<!-- -->
if(act[j].start>=act[i].end)
{<!-- -->
i=j;
selected[j]=1;
}
else
{<!-- -->
selected[j]=0;
}
}
}
int main()
{<!-- -->
cout<<"Please enter the number of activities:";
int n;
cin>>n;
int selected[n]; //If activity i is selected, then selected[i] is set to 1, otherwise it is set to 0
activity act[n];
\t
cout<<"Please enter the start and end time of the activity:"<<endl;
for(int i=1;i<=n;i + + )
{<!-- -->
cin>>act[i].start>>act[i].end;
}
act[0].start=-1;
act[0].end=-1;
sort(act + 1,act + n + 1,cmp); //act + 1 represents the 2nd element (i=1, 1st activity)
activity_select(n,selected,act);
cout<<"The following activities are selected:"<<endl;
for (int i=1; i<=n; i + + )
{<!-- -->
if (selected[i]==1)
{<!-- -->
cout<<i<<" ";
}
}
return 0;
}
3. Backpack problem
3.1 Problem description
?1. Suppose there is
n
n
n items, each item
i
i
The corresponding value of i is
v
i
v_i
vi?, weight
w
i
w_i
wi?. The backpack can only contain a weight of
m
m
m’s items. Each item can only be taken
1
1
1 piece, can be divided. The question is how to put the items in the backpack to maximize their value?
?2. Greedy strategy: (1) Every time you pick the item with the highest value and put it into your backpack, is the result the best? (2) Is the result obtained by picking the smallest weight item into the backpack each time optimal? (3) Every time you select the item with the greatest value per unit weight, does it have the highest value?
?3. It can be proved by mathematical induction that our greedy strategy should be to select the item with the greatest value per unit weight each time.
3.2 Code writing
#include<bits/stdc + + .h>
using namespace std;
struct item_type
{<!-- -->
float weight; //item weight
float value; //Item value
float per_item_value; //value of items per unit weight
float rate; //Use percentage
};
bool cmp(item_type a, item_type b)
{<!-- -->
return a.per_item_value > b.per_item_value;
}
int main()
{<!-- -->
int n; //n items
float c; //The backpack capacity is c
cout << "Enter the number of items and backpack capacity:" << endl;
cin >> n >> c;
item_type item[n];
item[0].per_item_value=0;
item[0].rate=0;
item[0].value=0;
item[0].weight=0;
cout << "Enter the value and weight of each item in turn:" << endl;
for (int i = 1; i <= n; i + + )
{<!-- -->
cin >> item[i].value >> item[i].weight;
item[i].per_item_value = item[i].value / item[i].weight;//calculate cost performance
item[i].rate = 0;//Initialization usage rate
}
sort(item + 1, item + n + 1, cmp);
float sum = 0;
int j = 1;
for (j = 1; j < n; j + + )
{<!-- -->
if (item[j].weight <= c)
{<!-- -->
item[j].rate = 1;
sum = sum + item[j].value;
c = c - item[j].weight; //c is always updated
cout << "The weight is:" << item[j].weight << "The item with the value: " << item[j].value << " is put into the backpack, and the proportion is: " << item[j].rate << endl;
}
else
break;
}
//Items are not loaded yet
if (j < n)
{<!-- -->
item[j].rate = c / item[j].weight;
c = c - item[j].rate * item[j].weight;
sum = sum + item[j].rate * item[j].value;
cout << "The weight is:" << item[j].weight << "The item with the value: " << item[j].value << " is put into the backpack, and the proportion is: " << item[j].rate << endl;
cout << "The remaining capacity of the backpack is:" << c;
cout << "Total value:" << sum;
}
return 0;
}
