Mixtures Problem Using Dynamic Programming in C++

Filed Under: C++
Mixtures Problem Using Dynamic Programming

In this article, we’ll learn to solve the mixtures problem using dynamic programming in C++. The mixtures problem is a well-known dynamic programming problem on SPOJ (Sphere Online Judge). You can not skip this problem as it’s a perfect problem to practice dynamic programming. So without wasting time, let’s get started.

Problem Statement for Mixtures Problem

There are N mixtures of different colors. The colors of these mixtures range from 0 to 99. Combining two mixtures generates a new mixture and some amount of smoke. The rules to combine two mixtures are:

Let the colors of the two mixtures be ‘a’ and ‘b’.

The colour of the resultant mixture: (a + b) % 100.

Smoke generated: a * b

Find out the minimum amount of smoke generated by mixing all the mixtures.

Input Format for Mixtures Problem in C++

The first line of input will be integer N. The following line will contain N integers denoting the colors of the mixture.

For example,

Input:
2
18 19
Solution:
342

Input:
3
40 60 20
Solution:
2400

Approach for Solving Mixtures Problem

How To Deal With Dynamic Programming Problems

Dynamic programming is the combination of recursion and memoization. We use dynamic programming because it makes the solution many times more optimum than recursive solutions. In dynamic programming solutions, we try to avoid recalculations of overlapping subproblems.

Pseudocode

Below is the step-by-step process that we’ll follow to code the solution.

  • We’ll combine only two mixtures at a time.
  • To minimize the resultant smoke, we’ll evaluate all possible subproblems.
  • Divide the input array into two parts.
    • Part 1: [m1, m2, m3, …….., ma]
    • Part 2: [ma + 1, m2, m3, …….., mn]
  • This problem is similar to the matrix chain multiplication problem.
  • Let’s represent the resultant smoke by combining [m1, m2, m3, …….., ma] = f(1, a)
  • Similarly, the resultant smoke by combining [ma + 1, m2, m3, …….., mn] = f(a + 1, n)
  • Recurrence relation : f(i, j) = f(i, k) + f(k + 1, j) + CumulativeSum(i, k) * CumulativeSum(k + 1, m)
  • CumulativeSum= summation from i=0 to k(a[i]%100)
  • Base case: if(i == j). i.e. if only one element is left.
    • Output: 0
    • Because a single mixture will not produce any smoke.

Robot And Paths Problem Using Dynamic Programming In C++ Program

#include <iostream>
#include <climits>

using namespace std;

int a[1000];
long long dp[1000][1000];

// function to evaluate the cumulative sum
long long sum(int s,int e)
{
	long long ans=0;

	for(int i=s;i<=e;i++)
	{
		ans+=a[i];
		ans%=100;
	}

	return ans;
}

long long mixtures(int i, int j)
{
	// base case 
	if(i >= j)
	{
		return 0;
	}

	// lookup step --> overlapping subproblem
	if(dp[i][j] != -1)
	{
		return dp[i][j];
	}

	// we need to break our expression at every possible k
	dp[i][j] = INT_MAX;

	for(int k = i;k <= j;k++)
	{
		// recursive relation
		dp[i][j] = min(dp[i][j], mixtures(i, k) + mixtures(k + 1, j) + sum(i, k) * sum(k + 1, j));
	}

	return dp[i][j];
}

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

	cout << "Enter the values of colours" << endl;

	for(int i = 0; i < n; i++)
	{
		//read n integers
		cin >> a[i];
	}

	// initialize the dp array with -1
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			dp[i][j] = -1;
		}
	}
	
	cout << "The minimum amount of smoke generated on mixing all the colours will be: " << mixtures(0, n - 1) << endl;

	return 0;
}
Mixtures Problem Code
Mixtures Problem Code

Output

Mixtures Problem Output
Mixtures Problem Output

Conclusion

Today, we solved the mixtures problem using dynamic programming in C++. We used the concept of recursion + memoization (Dynamic Programming) to solve this problem. We used the bottom-up approach to develop this solution. In the end, we 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/60732/remove-consecutive-duplicates-from-string-cpp

https://www.journaldev.com/59833/generate-strings-from-codes-cpp

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