This is a C++ Program that Solves Mixtures Problem using Dynamic Programming technique.
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.
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.
Case-1:
number of mixtures - 2 Initial color of mixtures - 18, 19 Minimum amount of smoke produced in mixing all mixtures together - 342
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.
#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;
}
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.
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.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Data Structure Books
- Apply for Data Structure Internship
- Buy Programming Books
- Practice Programming MCQs
- Apply for Computer Science Internship