Home »
Interview coding problems/challenges
Pizza Mania Problem
Pizza Mania Problem: In this article, we are going to see how to solve the pizza mania problem efficiently with dynamic programming? And, it can be featured in any interview rounds.
Submitted by Radib Kar, on April 19, 2020
Problem statement:
There is a shop which sells pizza of three different sizes- Small, Medium, and Large Pizza. IncludeHelp is crazy for Pizzas. A small Pizza has an area of 'S' unit2, a medium Pizza has an area of 'M' unit2 and a large Pizza has an area of 'L' unit2. Cost of Small, medium and Large Pizza is 'CS' , 'CM', and 'CL' respectively. IncludeHelp wants at least 'X' unit2 of pizza. What is the minimum amount of money needed to buy at least X unit2 of Pizza? If more than one arrangement is possible, choose that one which requires Least Money. Two arrangements are said to be different if They have different quantities of Small, medium, or large pizzas!
Input:
Input contains 6 integers-
X: total area of pizza needed (at least)
S: area of small sized pizza
M: area of medium sized pizza
L: area of large sized pizza
CS: cost of small sized pizza
CM: cost of medium sized pizza
CL: cost of large sized pizza
Output:
Minimum amount of money needed
Constraints
1<=X<=500
1<=S< M< L<=100
1<=CS< CM<CL=1000
Example:
Input:
X : 17
S : 4
M : 6
L : 12
CS: 40
CM: 60
CL: 100
Output:
160
Explanation:
IncludeHelp wants at least 17 unit2 of Pizza
Few possible arrangements can be,
5 Small pizza (size of 5*4=20) amounting 200
4 small pizza, one medium pizza (size 4*4+6=22) amounting 220
3 small pizza, two medium pizza (size 3*4+2*6=24) amounting 240
...
1 large pizza and 1 medium pizza (size 1*6+1*12=18) amounting 160
And this is the optimal money. No other arrangements can lead to a more optimal solution for this problem( that means we can't minimize the money anymore).
So, how we can solve the above problem?
To understand the problem, we can figure out that it's quite similar to the knapsack problem with constraints that we have an infinite supply of the pizzas and the number of different kinds of pizzas is three. We need to achieve the total size of pizza while investing the minimum amount of money.
So, let,
Total area of pizza needed (at least) = X
Area of small sized pizza: S
Area of medium sized pizza: M
Area of large sized pizza: L
Cost of small sized pizza: CS
Cost of medium sized pizza: CM
Cost of large sized pizza: CL
Now,
f(X) = minimum amount of money to get at least X area of pizza
So, f(X) can be written recursively as,
f(X) = minimum(f(X-S) + CS, f(X-M) + CM, f(X-L) + CL
Where,
X-S >= 0, X-m >= 0, X-L >= 0
That means, we choose either of small, medium or large pizza whichever is feasible leading to minimum money for any sub-problem
Since the recursion tree would generate many overlapping subproblems we need to convert it into DP.
Solution Approach:
Converting the recursion into DP:
1) Declare arr[X+1] and initialize arr[0]=0 which is result for X=0;
2) for i=1 to X //for each size of pizza
// if a small pizza cut is possible then dps=i-S else 0
Set dps=(i-S)≤0?0:(i-S)
// if a medium pizza cut is possible then dpm=i-M else 0
Set dpm=(i-M)<=0?0:(i-M)
// if a large pizza cut is possible then dpm=i-L else 0
Set dpl=(i-L)<=0?0:(i-L)
// find the minimum for this sub-problem
arr[i]=min(arr[dps]+CS,arr[dpm]+CM,arr[dpl]+CL)
end for
3) Return arr[X] which is final result.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
int min(int x, int y, int z)
{
if (x <= y && x <= z)
return x;
if (y <= z)
return y;
return z;
}
void minimumMoney(int X, int S, int M, int L, int CS, int CM, int CL)
{
int arr[X + 1];
arr[0] = 0;
for (int i = 1; i <= X; i++) {
//check for valid pizza part
int dps = (i - S) <= 0 ? 0 : (i - S);
//check for valid pizza part
int dpm = (i - M) <= 0 ? 0 : (i - M);
//check for valid pizza part
int dpl = (i - L) <= 0 ? 0 : (i - L);
//find the minimum
arr[i] = min(arr[dps] + CS, arr[dpm] + CM, arr[dpl] + CL);
}
cout << "Minimum amount of money: " << arr[X] << endl;
}
int main()
{
int X, S, M, L, CS, CM, CL;
cout << "Enter X, total size(at least)\n";
cin >> X;
cout << "Enter S, small pizza size\n";
cin >> S;
cout << "Enter M, medium pizza size\n";
cin >> M;
cout << "Enter L, large pizza size\n";
cin >> L;
cout << "Enter CS,cost of small pizza \n";
cin >> CS;
cout << "Enter CM,cost of medium pizza \n";
cin >> CM;
cout << "Enter CL,cost of large pizza \n";
cin >> CL;
minimumMoney(X, S, M, L, CS, CM, CL);
return 0;
}
Output
RUN 1:
Enter X, total size(at least)
17
Enter S, small pizza size
4
Enter M, medium pizza size
6
Enter L, large pizza size
12
Enter CS,cost of small pizza
40
Enter CM,cost of medium pizza
60
Enter CL,cost of large pizza
100
Minimum amount of money: 160
RUN 2:
Enter X, total size(at least)
17
Enter S, small pizza size
3
Enter M, medium pizza size
6
Enter L, large pizza size
12
Enter CS,cost of small pizza
50
Enter CM,cost of medium pizza
60
Enter CL,cost of large pizza
100
Minimum amount of money: 160