I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).

15-11: Inventory Planning, p.411

The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next $n$ months. For each month $i$, the company knows the demand $d_i$, that is, the number of machines that it will sell. Let $D = \displaystyle\sum_{i=1}^{n} d_i $ be the total demand over the next $n$ months. The company keeps a full-time staff who provide labor to manufacture up to m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function $h(j)$ for $u = 1, 2, ... , D$, where $h(j) \ge 0$ for $1 \le j \le D$ and $h(j) \le h(j+1)$ for $j \le 1 \le D - 1$.
Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomical in $n$ and $D$.

In other words, problem asks to create dynamic programming algorithm that solves this problem.

So far, I came up the the following solution, and not sure if it is any good.
Optimal sub-problem: Let $MinCost(i,j)$ be the function that returns minimized cost of operation for past $i$ months, $j$ is the number of unsold machines left at the end of the month $i$.(Goal, is to calculate $MinCost(n,0)$, in other words, at the end of planning period(month $n$), there are no unsold machines.)

So, the DP recurrence is given by $MinCost(0,0) = 0$ and

$\quad MinCost(i,j) = \min\{MinCost(i-1,j-k) + c(k,j,i) + h(j) \mid 1 \le k \le D \}$

for $i+j > 0$; here, $c(k,j,i)$ is the function that calculates the costs of the production.

If my optimal sub-problem is correct, how do I create an algorithm to solve it?


CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting

  • recursive top-down (p363),
  • memoized (p365f) and
  • bottom-up (p366).

I suggest you try to adapt one of these.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.