[go: up one dir, main page]
Scribd
Upload
26 views5 pages

Greedy Algorithms Advanced

This document provides a comprehensive overview of Greedy Algorithms, including detailed explanations, C++ code examples, and real-world applications. It covers key problems such as the Activity Selection Problem and the Fractional Knapsack Problem, illustrating the greedy approach for each with step-by-step solutions and use cases. Visual diagrams are included to enhance understanding of the concepts presented.

Uploaded by

kuramdasusaiteja
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
26 views5 pages

Greedy Algorithms Advanced

This document provides a comprehensive overview of Greedy Algorithms, including detailed explanations, C++ code examples, and real-world applications. It covers key problems such as the Activity Selection Problem and the Fractional Knapsack Problem, illustrating the greedy approach for each with step-by-step solutions and use cases. Visual diagrams are included to enhance understanding of the concepts presented.

Uploaded by

kuramdasusaiteja
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Greedy Algorithms - In-depth Explanation with Visuals

This document provides an in-depth exploration of Greedy Algorithms with detailed explanations,

C++ code examples, and real-world applications. Each algorithm is explained step-by-step with the

optimal approach, use cases, and visual diagrams for better understanding.
1. Activity Selection Problem
The Activity Selection Problem involves selecting the maximum number of non-overlapping

activities, given their start and finish times.

Greedy approach works by sorting activities based on their finish times and then selecting activities

that don't overlap with the previously selected ones.

Dry Run Example:

Given Activities: A1(1,2), A2(3,4), A3(0,6), A4(5,7), A5(8,9)

1. Sort activities by finish time: A1(1,2), A2(3,4), A4(5,7), A5(8,9), A3(0,6)

2. Select A1 (finish time 2), A2 (finish time 4), A4 (finish time 7), A5 (finish time 9).

C++ Code Example:

```cpp

struct Activity {

int start, finish;

};

bool compare(Activity a, Activity b) {

return a.finish < b.finish;

}
void activitySelection(Activity arr[], int n) {

sort(arr, arr + n, compare);

int i = 0;

cout << "Activity " << i + 1 << " is selected" << endl;

for (int j = 1; j < n; j++) {

if (arr[j].start >= arr[i].finish) {

cout << "Activity " << j + 1 << " is selected" << endl;

i = j;

```

Use Case: This problem is commonly used in scheduling applications such as scheduling meetings

or conference sessions where time slots need to be assigned without overlap.


2. Fractional Knapsack Problem
In the Fractional Knapsack Problem, the goal is to maximize the value of items placed in a knapsack

with a limited weight capacity. We are allowed to take fractions of items, and the greedy approach

maximizes the value-to-weight ratio.

C++ Code Example:

```cpp

struct Item {

int value, weight;

};

bool compare(Item a, Item b) {

return (a.value / (double)a.weight) > (b.value / (double)b.weight);

double fractionalKnapsack(Item arr[], int W, int n) {

sort(arr, arr + n, compare);

double totalValue = 0.0;

for (int i = 0; i < n; i++) {


if (arr[i].weight <= W) {

totalValue += arr[i].value;

W -= arr[i].weight;

} else {

totalValue += arr[i].value * ((double)W / arr[i].weight);

break;

return totalValue;

```

Use Case: The Fractional Knapsack problem is useful in scenarios like cargo transportation, where

cargo items can be split into fractions to optimize for value-to-weight ratio.

You might also like