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

^{2}, a medium Pizza has an area of

*unit*

**'M'**^{2}and a large Pizza has an area of

*unit*

**'L'**^{2}. Cost of Small, medium and Large Pizza is

*,*

**'CS'***, and*

**'CM'***respectively. IncludeHelp wants at least '*

**'CL'***unit*

**X'**^{2}of pizza.

**What is the minimum amount of money needed to buy at least**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!

*X*unit^{2}of Pizza?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 unit^{2}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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions