# Greedy Algorithm

###### tags: `Greedy`

>Prerequisite: None

## Content
[ToC]

## Fractional Knapsack Problem

### Problem Statement

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In the [0/1 Knapsack problem](https://hackmd.io/@h-ZsK3uKQU-EzblplsWowA/DrArmor_DP1), we are not allowed to break items. We either take the whole item or don’t take it.

### Algorithm

In a greedy algorithm, we will always choose the best solution of the current choice, where the greedy will lead us to the optimal substructure. The correctness of greedy algorithm is extremely important.

First, we have to calculate the ratio of value and weight of item i. Then, we will sort the ratio and pick the item based on the value of ratio. When the current capacity of knapsack is not enough for item i, we can only pick the fraction of item i.

The proof of correctness can refer to CLRS.

function Fractional-Knapsack(Item[], n):
    sort by the ratio of the item;
    for i = 1 to n-1:
        if Item[i].weight+currentWeight <= W:
            currentWeight += Item[i].weight;
            currentValue += Item[i].value;
        else:
            currentValue += Ttem[i].ratio*(W-Item[i].weight);
    return currentValue;

### C++ Code

#include <iostream>
using namespace std;

struct Item{
    int value;
    int weight;
    double ratio;
};

bool cmp(struct Item a, struct Item b)
{
    return a.ratio > b.ratio;
}

void Fractional(int value[], int weight[], int W, int n){
    Item A[n];
    
    for(int i = 0; i < n; i++){
        A[i].weight = weight[i];
        A[i].value = value[i];
        A[i].ratio = (value[i]*1.00)/(weight[i]*1.00);
    }
    sort(A, A+n, cmp);
    int weight_sum = 0;
    double value_sum = 0.0;
    for(int i = 0; i < n; i++){
        if(weight_sum + A[i].weight <= W){
            weight_sum += A[i].weight;
            value_sum += A[i].value;
        }
        else{
            value_sum += (A[i].ratio)*(W-A[i].weight)*1.0;
            break;
        }
    }
    cout << value_sum << endl;
}

int main(){
    int value[] = {60,100,120};
    int weight[] = {10,20,30};
    int W = 50;
    int n = sizeof(value)/sizeof(value[0]);
    Fractional(value, weight, W, n);
    return 0;
}

## Activity Selection Problem

### Problem Statement

You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

### Algorithm

The greedy choice is similar to that of the previous question. We can sort the activities based on the finish time. Then, we can put the activities into the schedule based on the sorted finish time. Also, examine whether the current activity is available based on the comparison of the start time of current activity and the latest finish time of the schedule.

function Activity-Selector(A[]):
    sort the activities based on finish time;
    print(A[0].id);
    for i = 2 to n:
        if(A[i].start > curTime):
            curTime = A[i].finish;
            print(A[i].id);

### C++ Code

#include <iostream>

using namespace std;

struct activities{
    int start;
    int finish;
    int number;
};

bool cmp(activities a, activities b){
    return a.finish < b.finish;
}
void fun(int start[], int finish[], int n){
    activities A[n];
    for(int i = 0; i < n; i++){
        A[i].start = start[i];
        A[i].finish = finish[i];
        A[i].number = i;
    }
    sort(A, A+n, cmp);
    cout << A[0].number << " ";
    int curTime = A[0].finish;
    for(int i = 1; i < n; i++){
        if(A[i].start > curTime){
            curTime = A[i].finish;
            cout << A[i].number << " ";
        }
    }
}

int main(){
    int start[] =  {3, 1, 0, 5, 8, 5};
    int finish[] = {4, 2, 6, 7, 9, 9};
    int n = sizeof(start)/sizeof(start[0]);
    fun(start, finish, n);
    return 0;
}