Mixtures Problem using Dynamic Programming

This is a C++ Program that Solves Mixtures Problem using Dynamic Programming technique.

Problem Description

Harry Potter has n mixtures in front of him, arranged in a row. Each mixture has one of 100 different colors (colors have numbers from 0 to 99).

He wants to mix all these mixtures together. At each step, he is going to take two mixtures that stand next to each other and mix them together, and put the resulting mixture in their place.

When mixing two mixtures of colors a and b, the resulting mixture will have the color (a+b) mod 100.

Also, there will be some smoke in the process. The amount of smoke generated when mixing two mixtures of colors a and b is a*b.

Find out what is the minimum amount of smoke that Harry can get when mixing all the mixtures together.

Problem Solution

The problem is very similar to matrix multiplication problem. In the marix multiplication problem, when we multiply two matrices of the order (a,b) and (b,c), we get a matrix of the order (a,c). Here, when we mix two adjacent colors a and b, we will get (a+b)%100. So, we will proceed in similar fashion using bottom up dynamic programming and store the result of sub-problems in a matrix.

Expected Input and Output

Case-1:

number of mixtures - 2
Initial color of mixtures - 18, 19
Minimum amount of smoke produced in mixing all mixtures together - 342

Program/Source Code

Here is source code of the C++ Program to Solve Mixtures Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Free 30-Day C Certification Bootcamp is Live. Join Now!

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
int main()
```
```
{
```
```
    int i,j,k;
```
```
    int x;
```
```
    int t,n;
```
```
 
```

    cout<<"Enter the number of mixtures ";

```
    cin>>n;
```
```
    vector<int> a(n);
```
```
 
```

    vector<vector<pair<int, int> > > dp(n+1,vector<pair<int, int> >(n+1));

```
 
```

    cout<<"Enter the initial color of mixtures "<<endl;

```
    for(i=1;i<=n;i++)
```
```
    {
```
```
        cin>>dp[i][i].second;
```
```
        dp[i][i].first=0;
```
```
    }
```
```
 
```
```
    for(int gap=2;gap<=n;gap++)
```
```
    {
```
```
        for(i=1;i<=(n-gap+1);i++)
```
```
        {
```
```
            j=i+gap-1;
```
```
            dp[i][j].first=INT_MAX;
```
```
 
```
```
            for(k=i;k<j;k++)
```
```
            {
```

                //try for every value of k

                x=dp[i][k].first+dp[k+1][j].first+dp[i][k].second*dp[k+1][j].second;

```
                if(x<dp[i][j].first)
```
```
                {
```
```
                    dp[i][j].first=x;
```

                    dp[i][j].second=(dp[i][k].second+dp[k+1][j].second)%100;

```
                }
```
```
 
```
```
            }
```
```
 
```
```
 
```
```
        }
```
```
    }
```
```
 
```

    cout<<"The minimum amount of smoke that will be produced by mixing all the mixtures together is "<<endl;

```
    cout<<dp[1][n].first<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we will take input for the elements of the array. Then, we will create a matrix dp to store result of sub-problems. After processing the array, result will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ mixtures.cpp
$ ./a.out
Enter the number of mixtures 2
Enter the initial color of mixtures 
18 19
The minimum amount of smoke that will be produced by mixing all the mixtures together is 
342

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Double Helix Problem – Dynamic Programming Solutions

» Next - Trigraphs Problem using Dynamic Programming

Related Posts:

Recommended Articles: