Greedy Algorithms in C++

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

#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; 
}

#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; 
}

#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; 
}

#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; 
}

#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; 
}