Pizza Mania Problem
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.
Converting the recursion into DP:
C++ Implementation:
Output