Greedy Problem Join The Ropes Using C++

Filed Under: C++
Greedy Problem Join The Ropes Using C

Today, we’ll learn to solve the greedy problem join the ropes using C++. The identity of greedy problems is that you’ll always find some sort of greedy choice either by sorting or some other comparison. This problem involves the concept of heaps, so it’s a perfect problem to revise heaps as well as greedy concepts. There are high chances of getting a similar problem during various coding rounds and coding competitions. So without wasting any time, let’s go through the problem statement.

Also read: Greedy Problem Of Connecting Wires Using C++

Problem Statement

There are N ropes of different sizes. The cost of joining ropes of the size ‘A’ and ‘B’ is ‘A + B’. Find out the minimum cost of joining all the ropes.

For example,

N: 4
Ropes: [4, 3, 2, 6]
Min_Cost: 29

Explaination: (2 + 3) + (2 + 3 + 4) + (2 + 3 + 4 + 6) = 29

N: 3
Ropes: [12, 1, 7]
Min_Cost: 28

Explaination: (1 + 7) + (1 + 7 + 12) = 28

Approach for Solving Greedy Problem Join The Ropes

The general approach to dealing with greedy problems is the following.

  • Make a greedy choice. (Local Optimum)
  • Verify that it’s a valid greedy choice.
  • Sort the items based on greedy selection.
  • Start the selection from the sorted items. (Local optimum at each step leads to global optimum)

Key To Solving This Problem

Note that, this is a minimization problem. We have to join all the ropes.

  • Suppose that, during each join operation we have two ropes of sizes A and B respectively.
  • During each join operation:
    • cost = A + B;
    • To minimize the cost of the join operation, we can select A and B as small as possible.
    • To get the smallest ropes each time, we’ll use a min-heap.
  • The above steps indicate that we must select the ropes of minimum sizes each time we join two ropes.

Pseudocode

Below is the step by step process that we’ll follow to implement the algorithm.

  • Greedy Choice: Select the smaller ropes first.
  • Sorting the ropes in increasing order of length
    • sort(ropes.begin(), ropes.end());
  • Initialize a variable to store the answer.
    • int min_cost = 0;
  • Start iterating over the ropes vector.
    • for(int i = 0; i < N; i++)
    • During each iteration, fulfil the greedy choice. i.e. select the ropes of the least size. Add the cost of each operation to the answer.
      • min_cost += (smallest_rope_length + second_smallest_rope_length);
  • Finally return the answer.
    • return min_cost;

Greedy Problem Join The Ropes Using C++ Program

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int min_cost(vector <int> ropes, int N)
{
	// use a min heap to sort the ropes
	// in the ascending order
	// initialize this priority queue
	// with the elements of the vector
	// ropes, this way, we won't need to
	// push the elements into min-heap
	// separately
	priority_queue <int, vector <int>, greater <int>> pq(ropes.begin(), ropes.end());

	int min_cost = 0;

	// the code logic begins here
	while(pq.size() > 1)
	{
		// select two ropes of the least size
		// also, remove these ropes from the heap
		int A = pq.top();
		pq.pop();
		int B = pq.top();
		pq.pop();

		// add the cost of their join operation
		// into the final cost
		min_cost += (A + B);

		// push another rope of size (A + B) into
		// the min-heap as a result of the
		// join
		pq.push(A + B);

	}

	return min_cost;
}

int main()
{
	cout << "Enter the value of N" << endl;
	int N;
	cin >> N;

	cout << "Enter the length of the ropes" << endl;
	vector <int> ropes(N);

	for(int i = 0; i < N; i++)
	{
		int pos;
		cin >> pos;

		ropes[i] = pos;
	}

	cout << "The minimum cost needed to join all the ropes is: " << min_cost(ropes, N) << endl;

	return 0;
}
Program Code 3
Program Code

Output

Join The Ropes Output 2
Join The Ropes Output

Conclusion

In this article, we learned to solve the greedy problem join the ropes using C++. We used the STL(Standard Template Library) to make use of the heap data structure. We also implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/56574/first-occurrence-last-occurrence-functions-cpp

https://www.journaldev.com/56852/binary-trees-bfs-traversal-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors