Greedy algorithms are an important type of algorithm used in computer science. They are used to solve problems that involve making decisions based on the current best available information. In this article, we will discuss what a greedy algorithm is, how it works, and how it can be used to solve problems in the context of the course “Data Structures and Algorithms with C++”.
What is a Greedy Algorithm?
A greedy algorithm is an algorithm that makes decisions in a step-by-step process, always selecting the best possible solution at the time. In other words, it looks for the best immediate solution instead of considering all possible solutions at once. Greedy algorithms are used to solve problems that involve making decisions based on the current best available information. Greedy algorithms have the advantage of being fast and relatively simple to implement.
How Greedy Algorithms Work
Greedy algorithms work by making a series of decisions that are based on the best available option at each step. The algorithm starts by making an initial choice, and then it evaluates the available options. The algorithm then makes the decision that produces the best outcome, and it continues to make the best decision at each step until it has reached an optimal solution.
For example, consider the problem of scheduling a set of tasks. The greedy algorithm would start by making an initial choice for the first task, and then it would evaluate the available options for the second task. The algorithm would then make the decision that produces the best outcome for the second task, and it would continue to make the best decisions for each task until it has reached an optimal solution.
To illustrate how a greedy algorithm works, consider the following problem:
Given a list of numbers, find the largest subset of numbers such that the sum of the numbers in the subset is less than or equal to a given target number.
The greedy algorithm would start by looking at the first number in the list and determining if it is less than or equal to the target number. If it is, the number is added to the subset. The algorithm then moves on to the next number and repeats the process until either the target number is reached or all the numbers in the list have been examined.
Examples of Greedy Algorithms in C++
Now let’s look at an example of a greedy algorithm written in C++. The following code implements the algorithm for the problem described above:
#include <iostream>
#include <vector>
using namespace std;
// Function to find the largest subset of numbers
// such that the sum of the numbers in the subset
// is less than or equal to the given target number
void findMaxSubset(vector<int> &nums, int target)
{
int n = nums.size();
// Vector to store the subset
vector<int> subset;
// Variable to store the sum of the elements in the subset
int sum = 0;
// Iterate over all the elements
for (int i = 0; i < n; i++)
{
// If the current element is less than or equal to
// the target number, add it to the subset
if (nums[i] <= target)
{
subset.push_back(nums[i]);
sum += nums[i];
// If the sum is greater than the target number,
// remove the last element from the subset
if (sum > target)
{
sum -= subset.back();
subset.pop_back();
}
}
}
// Print the largest subset
for (int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
}
// Driver program to test the above function
int main()
{
vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
int target = 11;
findMaxSubset(nums, target);
return 0;
}
In the above code, the function findMaxSubset() implements the greedy algorithm to find the largest subset of numbers such that the sum of the numbers in the subset is less than or equal to the given target number. The algorithm starts by looking at the first number in the list and determining if it is less than or equal to the target number. If it is, the number is added to the subset. The algorithm then moves on to the next number and repeats the process until either the target number is reached or all the numbers in the list have been examined.
Now, let’s look at another example.
The Knapsack Problem
The knapsack problem is a classic example of a problem that can be solved using a greedy algorithm. The problem is to choose items from a list of available items so that the total value of the items is maximized while the total weight of the items is kept below a certain limit.
The algorithm starts by sorting the list of items by value. Then, the algorithm iterates through the list of items, starting with the most valuable item. For each item, the algorithm checks if the item’s weight is less than the remaining capacity of the knapsack. If so, the item is added to the knapsack and the remaining capacity is reduced by the item’s weight. If not, the item is skipped. The algorithm continues until all the items have been considered.
Here is the C++ code for the knapsack problem:
// Inputs:
// Item weights: int[ ] weights
// Item values: int[ ] values
// Knapsack capacity: int capacity
int knapsack(int weights[ ], int values[ ], int capacity) {
// Sort items by value
// Sort items in descending order by value
for(int i = 0; i < weights.size(); i++) {
for(int j = i + 1; j < weights.size(); j++) {
if(values[i] < values[j]) {
// Swap values
int tempValue = values[i];
values[i] = values[j];
values[j] = tempValue;
// Swap weights
int tempWeight = weights[i];
weights[i] = weights[j];
weights[j] = tempWeight;
}
}
}
// Greedy algorithm
int maxValue = 0;
int currentWeight = 0;
// Iterate over items
for(int i = 0; i < weights.size(); i++) {
// If item can fit in knapsack
if(currentWeight + weights[i] <= capacity) {
// Add item to knapsack
currentWeight += weights[i];
maxValue += values[i];
}
}
return maxValue;
}
Advantages and Disadvantages of Greedy Algorithms
Greedy algorithms have some advantages and disadvantages that must be considered when deciding if they are the right approach for a particular problem.
Advantages:
- Greedy algorithms are fast and relatively simple to implement.
- They can be used to solve a wide range of problems.
- They typically have good performance, especially when compared to other algorithms.
Disadvantages:
- Greedy algorithms are not always guaranteed to find the optimal solution to a problem.
- They can be difficult to debug.
- They can be computationally intensive.
Conclusion
In this article, we discussed what a greedy algorithm is, how it works, and how it can be used to solve problems in the context of the course “Data Structures and Algorithms with C++”. We also looked at an example of a greedy algorithm written in C++ and discussed the advantages and disadvantages of using greedy algorithms.
Exercises
Write a greedy algorithm to find the minimum number of coins needed to make a given amount of change.
#include <iostream>
#include <vector>
using namespace std;
// Function to find the minimum number of coins needed
// to make a given amount of change
int findMinCoins(vector<int> coins, int amount)
{
// Sort the coins in descending order
sort(coins.begin(), coins.end(), greater<int>());
// Initialize the number of coins needed
int numCoins = 0;
// Iterate over each coin
for (int i = 0; i < coins.size(); i++)
{
// Calculate the number of coins needed
numCoins += (amount / coins[i]);
// Update the amount
amount = (amount % coins[i]);
}
return numCoins;
}
// Driver program to test the above function
int main()
{
vector<int> coins = {1, 5, 10, 25};
int amount = 34;
cout << "Minimum number of coins needed: "
<< findMinCoins(coins, amount);
return 0;
}
Write a greedy algorithm to find the maximum number of items that can fit into a knapsack of a given capacity.
#include <iostream>
#include <vector>
using namespace std;
// Structure for an item which stores weight and corresponding
// value of the item
struct Item
{
int value, weight;
};
// Function to find the maximum value that can be put in a knapsack of
// capacity W
int knapSack(int W, vector<Item> &items)
{
// sort the items in descending order of value
sort(items.begin(), items.end(),
[](const Item& a, const Item& b)
{
return a.value > b.value;
});
// stores the maximum value that can be attained
// with a knapsack of capacity W
int maxValue = 0;
// stores the remaining weight in the knapsack
int remainingWeight = W;
// Iterate over all the items
for (int i = 0; i < items.size(); i++)
{
// if the current item can fit in the knapsack
if (remainingWeight - items[i].weight >= 0)
{
// add it to the knapsack
maxValue += items[i].value;
// decrease the remaining weight
remainingWeight -= items[i].weight;
}
}
return maxValue;
}
// Driver program to test above function
int main()
{
// vector to store the items
vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
// Knapsack capacity
int W = 50;
cout << "Maximum value that can be put in knapsack of capacity "
<< W << " is " << knapSack(W, items);
return 0;
}
Write a greedy algorithm to find the minimum number of coins needed to make a given amount of change.
#include <iostream>
#include <vector>
using namespace std;
// Function to find the minimum number of coins needed
// to make a given amount of change
int findMinCoins(vector<int> coins, int amount)
{
// Sort the coins in descending order
sort(coins.begin(), coins.end(), greater<int>());
// Initialize the number of coins needed
int numCoins = 0;
// Iterate over each coin
for (int i = 0; i < coins.size(); i++)
{
// Calculate the number of coins needed
numCoins += (amount / coins[i]);
// Update the amount
amount = (amount % coins[i]);
}
return numCoins;
}
// Driver program to test the above function
int main()
{
vector<int> coins = {1, 5, 10, 25};
int amount = 34;
cout << "Minimum number of coins needed: "
<< findMinCoins(coins, amount);
return 0;
}
Write a greedy algorithm to find the maximum number of items that can fit into a knapsack of a given capacity.
#include <iostream>
#include <vector>
using namespace std;
// Structure for an item which stores weight and corresponding
// value of the item
struct Item
{
int value, weight;
};
// Function to find the maximum value that can be put in a knapsack of
// capacity W
int knapSack(int W, vector<Item> &items)
{
// sort the items in descending order of value
sort(items.begin(), items.end(),
[](const Item& a, const Item& b)
{
return a.value > b.value;
});
// stores the maximum value that can be attained
// with a knapsack of capacity W
int maxValue = 0;
// stores the remaining weight in the knapsack
int remainingWeight = W;
// Iterate over all the items
for (int i = 0; i < items.size(); i++)
{
// if the current item can fit in the knapsack
if (remainingWeight - items[i].weight >= 0)
{
// add it to the knapsack
maxValue += items[i].value;
// decrease the remaining weight
remainingWeight -= items[i].weight;
}
}
return maxValue;
}
// Driver program to test above function
int main()
{
// vector to store the items
vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
// Knapsack capacity
int W = 50;
cout << "Maximum value that can be put in knapsack of capacity "
<< W << " is " << knapSack(W, items);
return 0;
}
Write a greedy algorithm to find the maximum number of jobs that can be scheduled in a given time.
#include <iostream>
#include <vector>
using namespace std;
// Structure for a job which stores start and finish time
struct Job
{
int start, finish;
};
// Function to find the maximum number of jobs that can be scheduled
// in a given time
int maxJobs(vector<Job> &jobs)
{
// sort the jobs in ascending order of finish time
sort(jobs.begin(), jobs.end(),
[](const Job& a, const Job& b)
{
return a.finish < b.finish;
});
// stores the maximum number of jobs that can be scheduled
int maxJobs = 0;
// stores the last finish time of a scheduled job
int lastFinishTime = 0;
// Iterate over all the jobs
for (int i = 0; i < jobs.size(); i++)
{
// if the current job can be scheduled after the
// last scheduled job
if (jobs[i].start >= lastFinishTime)
{
// increment the number of jobs
maxJobs++;
// update the last finish time
lastFinishTime = jobs[i].finish;
}
}
return maxJobs;
}
// Driver program to test above function
int main()
{
// vector to store the jobs
vector<Job> jobs = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
cout << "Maximum number of jobs that can be scheduled: "
<< maxJobs(jobs);
return 0;
}