Minimum Cost Pizza Selection

Problem Overview

You may buy any number of small, medium, and large pizzas, and you only need the total area to reach x.

Intuition

You may buy any number of small, medium, and large pizzas, and you only need the total area to reach x. That is an unbounded knapsack: the cheapest way to make each exact area is the cheapest way to make a smaller area plus one more pizza. Extra area past x never helps, because every price is positive.

Algorithm

1Drop a pizza when another one has at least as much area and a better price.
2Let dp[i] be the minimum cost of exactly area i, with dp[0] = 0.
3The table runs through x + maxSize - 1, the farthest one last pizza can overshoot.
4From each reachable area below x, try each remaining pizza and relax the next area.
5When an area is at least x, record its cost and do not buy anything more from there.
6Return the smallest recorded cost.

Example Walkthrough

Input: x = 5, areas 2, 3, 4 with costs 3, 4, 5

1. One medium pizza and one small pizza cover area 5 for cost 7.
2. Two medium pizzas cover area 6 for cost 8.
3. One large pizza is only area 4, so it still needs another pizza.

Output: 7

Common Pitfalls

• The target is at least x, so a little extra area can be cheaper than an exact fit.
• Do not keep buying after the area already reaches x.
• Skip unreachable areas instead of adding a cost onto an infinite sentinel.
• A larger pizza with a lower or equal price makes the smaller one useless.

Minimum Cost Pizza Selection.java

Java

// Approach: Unbounded knapsack for the cheapest way to reach area at least x
// with three pizza sizes. dp[i] is the minimum cost of exactly area i.
// Only reachable areas below x are expanded, because every cost is positive,
// so buying more after x cannot help. A pizza is ignored when another pizza
// gives at least as much area for a strictly better price.
// The last pizza overshoots by less than the largest size, so the table
// stops at x + maxSize - 1.
// Complexity: O(x) time and O(x) extra space.
import java.util.Arrays;

class Solution {
    public int minimumCost(int x, int s, int m, int l, int cs, int cm, int cl) {
        int[] area = { s, m, l };
        int[] cost = { cs, cm, cl };
        boolean[] skip = new boolean[3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j && area[j] >= area[i] && cost[j] <= cost[i]
                        && (area[j] > area[i] || cost[j] < cost[i]))
                    skip[i] = true;
            }
        }

        int maxSize = Math.max(s, Math.max(m, l));
        int limit = x + maxSize - 1;
        int inf = Integer.MAX_VALUE / 4;
        int[] dp = new int[limit + 1];
        Arrays.fill(dp, inf);
        dp[0] = 0;

        int answer = inf;
        for (int i = 0; i <= limit; i++) {
            if (dp[i] == inf)
                continue;
            if (i >= x) {
                answer = Math.min(answer, dp[i]);
                continue;
            }
            for (int t = 0; t < 3; t++) {
                if (skip[t])
                    continue;
                int next = i + area[t];
                if (next <= limit)
                    dp[next] = Math.min(dp[next], dp[i] + cost[t]);
            }
        }
        return answer;
    }
}

Was this solution helpful?