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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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


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.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int i,j,k;
  7.     int x;
  8.     int t,n;
  10.     cout<<"Enter the number of mixtures ";
  11.     cin>>n;
  12.     vector<int> a(n);
  14.     vector<vector<pair<int, int> > > dp(n+1,vector<pair<int, int> >(n+1));
  16.     cout<<"Enter the initial color of mixtures "<<endl;
  17.     for(i=1;i<=n;i++)
  18.     {
  19.         cin>>dp[i][i].second;
  20.         dp[i][i].first=0;
  21.     }
  23.     for(int gap=2;gap<=n;gap++)
  24.     {
  25.         for(i=1;i<=(n-gap+1);i++)
  26.         {
  27.             j=i+gap-1;
  28.             dp[i][j].first=INT_MAX;
  30.             for(k=i;k<j;k++)
  31.             {
  32.                 //try for every value of k
  33.                 x=dp[i][k].first+dp[k+1][j].first+dp[i][k].second*dp[k+1][j].second;
  34.                 if(x<dp[i][j].first)
  35.                 {
  36.                     dp[i][j].first=x;
  37.                     dp[i][j].second=(dp[i][k].second+dp[k+1][j].second)%100;
  38.                 }
  40.             }
  43.         }
  44.     }
  46.     cout<<"The minimum amount of smoke that will be produced by mixing all the mixtures together is "<<endl;
  47.     cout<<dp[1][n].first<<endl;
  49.     return 0;
  50. }
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
$ 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 

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


Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.