Minimum Cost Pizza Selection Using Dynamic Programming

Introduction

Given three types of pizzas — Small, Medium, and Large — we know their respective areas and costs.

The goal is to buy pizzas such that the total area is at least x, while spending the minimum possible amount of money.

We can buy any number of pizzas of each type.

This problem can be solved efficiently using Dynamic Programming (DP).

Problem Statement

We are given:

s → Area of Small pizza
m → Area of Medium pizza
l → Area of Large pizza
cs → Cost of Small pizza
cm → Cost of Medium pizza
cl → Cost of Large pizza
x → Required minimum area

We need to return the minimum cost required to obtain a total pizza area of at least x.

Example

Input:
x = 16
s = 3, m = 6, l = 9
cs = 50, cm = 150, cl = 300

Output:
300

One possible solution is:

6 Small pizzas

Total Area = 6 × 3 = 18
Total Cost = 6 × 50 = 300

Since 18 >= 16, this satisfies the requirement.

Therefore:

Minimum Cost = 300

Key Idea

At first, we might think that choosing the pizza with the lowest cost is enough.

But that is not always correct.

For example:

Small Pizza:
Area = 3
Cost = 50

Large Pizza:
Area = 9
Cost = 300

A small pizza is cheaper individually, but we may need several small pizzas to reach the required area.

Therefore, we need to consider different combinations of pizzas.

Dynamic Programming allows us to calculate the minimum cost for every required area and reuse those results.

Dynamic Programming Definition

Let:

dp[i]

represent the minimum cost required to obtain at least i area.

Initially:

dp[0] = 0

because we need no money to obtain zero area.

For every i, we can choose one of the three pizzas.

Choose Small Pizza

If we buy a Small pizza:

dp[i - s] + cs

The previous required area is i - s, and we add the cost of the Small pizza.

Choose Medium Pizza

dp[i - m] + cm

Choose Large Pizza

dp[i - l] + cl

Therefore:

dp[i] = minimum of

dp[i - s] + cs
dp[i - m] + cm
dp[i - l] + cl

Handling Area Greater Than x

The problem says the total area should be at least x, not exactly x.

For example:

x = 16

An area of:

is acceptable.

This is why when a pizza itself has an area greater than the currently required area, buying that pizza alone is already enough.

For example:

Required area = 5
Large pizza area = 9
Large pizza cost = 300

Buying one Large pizza gives:

9 >= 5

so the cost is simply:

Algorithm

Create a DP array of size x + 1.
Set dp[0] = 0.
Initialize the remaining values with a large value.
For every area from 1 to x:
- Consider buying a Small pizza.
- Consider buying a Medium pizza.
- Consider buying a Large pizza.
Take the minimum cost among the three choices.
Return dp[x].

Java Implementation

class Solution {
    public int minimumCost(int x, int s, int m, int l,
                           int cs, int cm, int cl) {

        int[] dp = new int[x + 1];

        // Initialize DP array
        for (int i = 1; i <= x; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        dp[0] = 0;

        for (int i = 1; i <= x; i++) {

            // Choose Small Pizza
            if (i >= s) {
                dp[i] = Math.min(dp[i],
                        dp[i - s] + cs);
            } else {
                dp[i] = Math.min(dp[i], cs);
            }

            // Choose Medium Pizza
            if (i >= m) {
                dp[i] = Math.min(dp[i],
                        dp[i - m] + cm);
            } else {
                dp[i] = Math.min(dp[i], cm);
            }

            // Choose Large Pizza
            if (i >= l) {
                dp[i] = Math.min(dp[i],
                        dp[i - l] + cl);
            } else {
                dp[i] = Math.min(dp[i], cl);
            }
        }

        return dp[x];
    }
}

Code Explanation

1. Create the DP Array

int[] dp = new int[x + 1];

We need values from:

dp[0] to dp[x]

So the size is x + 1.

2. Initialize the DP Array

for (int i = 1; i <= x; i++) {
    dp[i] = Integer.MAX_VALUE;
}

Initially, we don't know the minimum cost for any area.

Therefore, we use Integer.MAX_VALUE as infinity.

dp[0] = 0;

Zero area requires zero cost.

3. Iterate Through Every Required Area

for (int i = 1; i <= x; i++) {

We calculate the minimum cost for every area from 1 to x.

Because smaller DP values are calculated first, they can be reused to calculate larger values.

4. Try Small Pizza

if (i >= s) {
    dp[i] = Math.min(dp[i],
            dp[i - s] + cs);
} else {
    dp[i] = Math.min(dp[i], cs);
}

If i >= s, we can use a previously calculated result:

dp[i - s]

and add the Small pizza cost:

+ cs

If i < s, one Small pizza already provides enough area.

For example:

i = 2
s = 3

One Small pizza gives area 3, which is already at least 2.

So its cost is simply cs.

5. Try Medium Pizza

if (i >= m) {
    dp[i] = Math.min(dp[i],
            dp[i - m] + cm);
} else {
    dp[i] = Math.min(dp[i], cm);
}

The same logic is applied to the Medium pizza.

6. Try Large Pizza

if (i >= l) {
    dp[i] = Math.min(dp[i],
            dp[i - l] + cl);
} else {
    dp[i] = Math.min(dp[i], cl);
}

Again, we calculate the cost using the Large pizza.

7. Return the Answer

return dp[x];

dp[x] contains the minimum cost required to obtain an area of at least x.

Dry Run

Consider:

x = 10

Small:
Area = 1
Cost = 10

Medium:
Area = 3
Cost = 20

Large:
Area = 10
Cost = 50

We can buy:

10 Small pizzas
Area = 10
Cost = 100

or:

4 Medium pizzas
Area = 12
Cost = 80

or:

1 Large pizza
Area = 10
Cost = 50

The minimum is:

Therefore:

Output = 50

The DP evaluates these possibilities automatically.

Why Greedy Does Not Work Reliably

A greedy approach might select the pizza with the lowest individual cost.

Suppose:

Small  → Area = 3, Cost = 50
Medium → Area = 6, Cost = 150
Large  → Area = 9, Cost = 300

The Small pizza has the lowest cost.

But if we need:

x = 16

we need six Small pizzas:

6 × 3 = 18 area
6 × 50 = 300 cost

Other combinations may use fewer pizzas but have a higher individual price.

Therefore, we need to compare combinations instead of simply choosing the cheapest pizza.

Why Dynamic Programming Works

This problem has two important properties.

1. Overlapping Subproblems

When calculating the minimum cost for different areas, the same smaller areas are repeatedly required.

For example:

dp[10]

may depend on:

dp[7]
dp[4]
dp[1]

These smaller values can be reused instead of calculating them again.

2. Optimal Substructure

The minimum cost for a larger area can be constructed from the minimum cost of a smaller area.

For example:

dp[i] = dp[i - s] + cs

If dp[i - s] already represents the minimum cost for the smaller area, adding one Small pizza gives one possible solution for i.

We compare it with the Medium and Large pizza choices and keep the minimum.

Complexity Analysis

There are x DP states.

For each state, we check exactly three pizza types.

Therefore:

Time Complexity: O(x)

The DP array contains x + 1 elements:

Space Complexity: O(x)

Conclusion

The Minimum Cost Pizza Selection problem is a good example of the Unbounded Knapsack / Dynamic Programming pattern.

The important observation is that:

We can buy any number of pizzas.
We need an area of at least x.
Each pizza type can be selected multiple times.
We need to compare all possible choices efficiently.

By maintaining:

dp[i] = minimum cost to obtain at least i area

we can solve the problem in:

Time:  O(x)
Space: O(x)

This approach is efficient enough because the constraint is only:

x <= 500