Juice Bottling

Tags

Juice Bottling

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

You have n units of juice and an array prices where prices[i] is the revenue obtained by selling a bottle containing exactly i units of juice (prices[0] = 0). Determine how to divide the n units into bottles to maximize total revenue. Return the bottle sizes used.

Intuition

This is the classic rod cutting problem applied to juice. For n units of juice, we choose a first bottle of size k (earning prices[k]) and then optimally bottle the remaining n - k units. Overlapping subproblems arise because multiple first-cut choices lead to the same remaining quantity.

Approach

  1. Create an array dp of size n+1, where dp[i] is the maximum revenue from i units. Set dp[0] = 0.
  2. Create a cuts array to reconstruct the solution.
  3. For each quantity i from 1 to n:
    • For each bottle size k from 1 to i:
      • If prices[k] + dp[i-k] > dp[i]:
        • Update dp[i] = prices[k] + dp[i-k]
        • Record cuts[i] = k
  4. Backtrack from cuts[n] to build the list of bottle sizes.
  5. Return the list.

Pseudocode

function juiceBottling(prices):
    n = length(prices) - 1
    dp = array of size (n+1), filled with 0
    cuts = array of size (n+1), filled with 0

    for i from 1 to n:
        for k from 1 to i:
            if prices[k] + dp[i-k] > dp[i]:
                dp[i] = prices[k] + dp[i-k]
                cuts[i] = k

    // Reconstruct bottle sizes
    bottles = []
    remaining = n
    while remaining > 0:
        bottles.append(cuts[remaining])
        remaining -= cuts[remaining]

    return bottles

Time & Space Complexity

MeasureComplexityJustification
TimeO(n^2)Two nested loops: for each of n quantities, try up to n bottle sizes
SpaceO(n)DP array and cuts array

Key Insights

  • This is structurally identical to the rod cutting problem. The "price per unit length" framing is the same as "price per bottle size."
  • Greedy (e.g., always pick the bottle with the best price-per-unit) does not work because combinations of smaller bottles may out-earn larger ones.
  • If prices[n] >= dp[n] for all possible decompositions, a single bottle of size n is optimal — but this must be discovered by DP, not assumed.
  • The problem can also be solved top-down with memoization; the recurrence is dp[i] = max over k of (prices[k] + dp[i-k]).

Edge Cases

  • n = 0: no juice to bottle; revenue is 0, return an empty list.
  • All prices are 0 except prices[1]: sell all juice in unit-size bottles.
  • prices[n] is the highest: one bottle of size n is optimal.
  • Prices decrease per unit for larger bottles: smaller bottles are always preferred; the DP discovers this.
  • n = 1: the only option is a single bottle of size 1.

Linked mentions