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' unit², a medium Pizza has an area of 'M' unit² and a large Pizza has an area of 'L' unit². Cost of Small, medium and Large Pizza is 'CS' , 'CM', and 'CL' respectively. IncludeHelp wants at least 'X' unit² of pizza. What is the minimum amount of money needed to buy at least X unit² 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