Mixtures Problem Using Dynamic Programming in C++

Filed Under: C++

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++)
{
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;
}
```

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.