1511 Inventory planning
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 = \sum_{i = 1}^n d_i$ be the total demand over the next $n$ months. The company keeps a fulltime staff who provide labor to manufacture up to $m$ machines per month. If the company needs to make more than $m$ machines in a given month, it can hire additional, parttime 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 $j = 1, 2, \ldots, D$, where $h(j) \ge 0$ for $1 \le j \le D$ and $h(j) \le h(j + 1)$ for $1 \le j \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 polyomial in $n$ and $D$.
We state the subproblem $(k, s)$ as "What is the cheapest way to satisfy all the demands of months $k, \ldots, n$ when we start with a surplus of s before the $k$th month?" A plan for the subproblem $(k, s)$ would specify the number of machines to manufacture for each month $k, \ldots, n$ such that demands are satisfied.
In some optimal plan $P$ to $(k, s)$, let $f^*$ machines be maufactured in month $k$. Thus, the surplus $s'$ in month $k + 1$ is $s + f^*  d_k$. Let $P'$ be the part of the plan $P$ for months $k + 1, \ldots, n$. We claim that $P'$ is an optimal plan for the subproblem $(k + 1, s')$. Why? Suppose $P'$ were not an optimal plan and let $P''$ be an optimal plan for $(k + 1, s')$. If we modify plan $P$ by cutting out $P'$ and pasting in $P''$ (i.e., by using plan $P''$ for months $k + 1, \ldots, n$), we obtain another plan for $(k, s)$ which is cheaper than plan $P$ . Thus, we obtain a contradiction to the assumption that plan $P$ was optimal.
Let $cost[k, s]$ denote the cost of an optimal plan for $(k, s)$, and let $f$ denote the number of machines that can be manufactured in month $k$. The bounds for $f$ are as follows:

At least the number of machines so that (along with surplus $s$) there are enough machines to satisfy the current month's demand. Let us denote this lower bound by $L(k, s)$. We have
$$L(k, s) = \max(d_k  s, 0).$$

At most the number of machines such that there are enough machines to satisfy the demands of all the following months. Let us denote this upper bound by $U(k, s)$. We have
$$U(k, s) = \Bigg(\sum_{i = k}^n d_i \Bigg)  s.$$
For the last month, we need only manufacture the minimum required number of machines, given by $L(n, s)$. For other months, we examine the costs of manufacturing all feasible numbers of machines and see which choice gives us the cheapest plan. We can now write the recurrence for cost as the following:
$$ cost[k, s] = \begin{cases} c \cdot \max(L(n, s)  m, 0) + h(s + L(n, s)  d_n) & \text{if $k = n$}, \\ \min\limits_{L(k, s) \le f \le U(k, s)} \Big\{cost[k + 1, s + f  d_k] + c \cdot \max(f  m, 0) + h(s + f  d_k)\Big\} & \text{if $0 < k < n$}. \end{cases} $$
The recurrence suggests how to build an optimal plan in a bottomup fashion. We now present the algorithm for constructing an optimal plan.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  INVERTORYPLANNING(n, m, c, D, d, h) let cost[1..n, 0..D] and make[1..n, 0..D] be new tables // Compute cost[n, 0..D] and make[n, 0..D]. for s = 0 to D f = max(d[n]  s, 0) cost[n, s] = c * max(f  m, 0) + h(s + f  d[n]) make[n, s] = f // Compute cost[1..n  1, 0..D] and make[1..n  1, 0..D]. U = d[n] for k = n  1 downto 1 U = U + d[k] for s = 0 to D cost[k, s] = ∞ for f = max(d[k]  s, 0) to U  s val = cost[k + 1, s + f  d[k]] + c * max(f  m, 0) + h(s + f  d[k]) if val < cost[k, s] cost[k, s] = val make[k, s] = f print cost[1, 0] PRINTPLAN(make, n, d) 
1 2 3 4 5  PRINTPLAN(make, n, d) s = 0 for k = 1 to n print "For month" k "manufacture" make[k, s] "machines" s = s + make[k, s]  d[k] 
In $\text{INVENTORYPLANNING}$, we build the solution month by month, starting from month $n$, moving backward toward month $1$. First, we solve the subproblem for the last month, for all surpluses. Then, for each month and for each surplus entering that month, we calculate the cheapest way to satisfy demand for that month based on the solved subproblems of the next month.
 $f$ is the number of machines that we try to manufacture in month $k$.
 $cost[k, s]$ holds the cheapest way to satisfy demands of months $k, \ldots, n$, with a net surplus of s left over at the beginning of month $k$.
 $make[k, s]$ holds the number of machines to manufacture in month $k$ and the surplus $s$ of an optimal plan. We will use this table to reconstruct the optimal plan.
We first initialize the base cases, which are the cases for month $n$ starting with surplus $s$, for $s = 0, \ldots, D$. If $d_n > s$, it suffices to manufacture $d_n  s$ machines, since we need not keep any surplus after month $n$. If $d_n \le s$, we need not manufacture any machines at all.
We then calculate the total cost for month $n$ as the sum of hiring extra labor $c \cdot \max(f  m, 0)$ and the inventory costs for leftover surplus $h(s + f  d_n)$, which can be nonzero if we had started out with a large surplus.
The outer for loop of the next block of code runs down from month $n  1$ to $1$, thus ensuring that when we consider month $k$, we have already solved the subproblems of month $k + 1$.
The next inner for loop iterates through all possible values of $f$ as described.
For every choice of $f$ for a given month $k$, the total cost of $(k, s)$ is given by the cost of extra labor (if any) plus the cost of inventory (if there is a surplus) plus the cost of the subproblem $(k + 1, s + f  d_k)$. This value is checked and updated. Finally, the required answer is the answer to the subproblem $(1, 0)$, which appears in $cost[1, 0]$. That is, it is the cheapest way to satisfy all the demands of months $1, \ldots, n$ when we start with a surplus of $0$.
The running time of $\text{INVENTORYPLANNING}$ is clearly $O(nD^2)$. The space requirement is $O(nD)$. We can improve upon the space requirement by noting that we need only store the solution to subproblems of the next month. With this observation, we can construct an algorithm that uses $O(n + D)$ space.