What is Greedy Algorithm?

The Greedy Algorithm is to make the best choice at current stage when solving the problem. That is to say, instead of considering the global optimal solution, it only makes the local optimal solution in a certain sense.

Greedy Algorithm can not get global optimal solution for all problems, but it can produce global optimal solution or approximate solution for a wide range of problems.

In a word, greedy is from the local optimal solution to the global optimal solution.

The basic way to solve the greedy problem

  1. Establish a mathematical model to describe the problem.
  2. Divide the problem into several subproblems.
  3. Solve each subproblem to get the local optimal solution.
  4. Synthesize the local optimal solution of the subproblem into a solution of the original problem.

example

Knapsack problem（背包问题）

A traveler has a backpack that can hold at most M kg. Now there are n items. The weight of each item is W1, W2,…, WN respectively. The value of each item is C1, C2,…, CN respectively. You need to put the items into the backpack. How can you ensure the maximum value of the items in the backpack?

Input

  • The first line has two numbers. The first one describes the num of items. The second one describes your bag capacity.
  • The next n lines describe item’s heavy and value.
1
2
3
4
5
4 50					<- N M
10 60					<- Item1 W1 C1
20 100
30 120
15 45

Output

1
205

Solve

In the current situation, the most beneficial situation is to choose the items with more value and less weight. That is to choose the item with the highest cost performance (value / weight).

In summary, we first rank all items according to the price performance ratio from high to low.Then choose the most cost-effective item that the current backpack can hold.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

struct item
{
    double money;
    double heavy;
    double per;
};

bool cmp(struct item a, struct item b)
{
    return a.per > b.per;
}

int main()
{
    int n;
    double cap;
    cin >> n >> cap;
    
    /* 建立物品结构体 */
    struct item a[n];
    for(int i=0; i<n; i++)
    {
        cin >> a[i].heavy >> a[i].money;
        a[i].per = a[i].money / a[i].heavy;
    }
    
    /* 按性价比从高到低排序 */
    sort(a, a+n, cmp);
    
    /* 每次循环就相当于拿一次物品 */
    double sum=0;
    for(int i=0; i<n; i++)
    {
        if(cap > a[i].heavy)
        {
            sum += a[i].money;
            cap -= a[i].heavy;
        }
    }
    cout << sum << endl;
    
    return 0;
}