So I am trying to find the recurrence for this problem but I feel like it is missing something.

An ice cream shop is looking to minimize their operation costs, under the given constraints:

They are faced with costs of purchasing ice cream from a local distributor, where each order has a (potentially large) fixed delivery cost $shipping_cost$ as well as the price $price$ for each pint
To minimize delivery costs, they can buy more ice cream than needed for a given day, and keep it stored in their freezer overnight.
Their freezer can store $max capacity$ pints of ice cream at any time (includes both the shipment as well as any pints stored overnight)
However, storing extra ice cream overnight is not free, and it costs them $overnight cost$ dollars per pint (per night) to keep any additional ice cream frozen if they buy in advance.
Given a list of $daily demand$ (in pints) of ice cream for the next $num_days$ days, what is the minimum cost for the shop to be stocked up ready to meet their demands each day?


  • An integer $num\_days$, for the number of days
  • A list of $n$ integers demands, separated by a space, for the pints of ice cream demanded each day
  • An integer $max\_capacity$, for the capacity of their freezer
  • An integer $shipping\_cost$ , for the fixed cost of each shipment taken
  • An integer $price$, for the price they pay for each pint of ice cream
  • An integer $overnight\_cost$, the cost of storing a pint of ice cream for a day
  • $minCost[n]$ = the minimize cost on the nth day.
  • $iceCream[n]$ = the pints of ice cream demanded on the nth day

So this is what I thought of:

The whole price of ice cream should be the sum of pints * price, it will never change.

On day 1, the shop must pay shipping fee. minCost[0] = shipping_cost.

If the remaining ice cream cannot satisfy the demand on that day, the shop has to ship more, cost = shipping_cost + overnight_cost, so they should avoid this situation. Therefore, we only compare shipping_cost with overnight_cost.

$minCost[n] = min { shipping\_cost + minCost[n-1], overnight\_cost * iceCream[n] + minCost[n-1] }$

However, when max_capacity is not big enough, the remaining ice cream cannot satisfy the demand on next day, they have to ship.

if( ( max_capacity - iceCream[n-1] ) < iceCream[n] )
    minCost[n] = shipping_cost + minCost[n-1]

What is this missing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.