Caterer problem | Algorithms Notes
Let r[i] be the demand of clean napkins in the i-th day, i = 1 ~ n. In the end of day, the caterer must clean all dirty napkins. The caterer can send dirty napkins to a fast laundry with a cost c for each napkin and these napkin will become clean in the next day. Or, the caterer can send dirty napkins to a slow laundry with a cost d for each napkin and these napkins will become clean in three days. The caterer can purchase S clean napkins before the first day with a cost a for each clean napkin. Design an algorithm to find a purchase/laundry plan with the minimum cost subject to the demand.
Solution:
This problem can be solved by using minimum cost flow. Here, we use dynamic programming approach.
Let u[i] and v[i] be the number of napkins sent to a fast laundry and a slow laundry on the i-th day, respectively. The problems is to pick S, u, and v, such that aS + c![\sum_i u[i]](https://s0.wp.com/latex.php?latex=%5Csum_i+u%5Bi%5D&bg=ffffff&fg=333333&s=0 "\sum_i u[i]")
+ d![\sum_i v[i]](https://s0.wp.com/latex.php?latex=%5Csum_i+v%5Bi%5D&bg=ffffff&fg=333333&s=0 "\sum_i v[i]")
is minimized. It is obvious that u[n] = 0 and v[n] = r[n]. Thus, we objective function becomes aS + ![\sum_{i=1}^{n-1} c(r[i] - v[i]) + dv[i]](https://s0.wp.com/latex.php?latex=%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D+c%28r%5Bi%5D+-+v%5Bi%5D%29+%2B+dv%5Bi%5D&bg=ffffff&fg=333333&s=0 "\sum_{i=1}^{n-1} c(r[i] - v[i]) + dv[i]")
+dr[n]. Let K = ![dr[n] + c\sum_{i=1}^{n-1} r[i]](https://s0.wp.com/latex.php?latex=dr%5Bn%5D+%2B+c%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D+r%5Bi%5D&bg=ffffff&fg=333333&s=0 "dr[n] + c\sum_{i=1}^{n-1} r[i]")
. The objective function in fact becomes K + aS – (c – d)![\sum_{i=1}^{n-1} v[i]](https://s0.wp.com/latex.php?latex=%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D+v%5Bi%5D&bg=ffffff&fg=333333&s=0 "\sum_{i=1}^{n-1} v[i]")
. Intuitively, when S is fixed, our goal is to maximize the number of napkins sent to slow laundry.
Read full article from Caterer problem | Algorithms Notes
Let r[i] be the demand of clean napkins in the i-th day, i = 1 ~ n. In the end of day, the caterer must clean all dirty napkins. The caterer can send dirty napkins to a fast laundry with a cost c for each napkin and these napkin will become clean in the next day. Or, the caterer can send dirty napkins to a slow laundry with a cost d for each napkin and these napkins will become clean in three days. The caterer can purchase S clean napkins before the first day with a cost a for each clean napkin. Design an algorithm to find a purchase/laundry plan with the minimum cost subject to the demand.
Solution:
This problem can be solved by using minimum cost flow. Here, we use dynamic programming approach.
Let u[i] and v[i] be the number of napkins sent to a fast laundry and a slow laundry on the i-th day, respectively. The problems is to pick S, u, and v, such that aS + c
+ d is minimized. It is obvious that u[n] = 0 and v[n] = r[n]. Thus, we objective function becomes aS + +dr[n]. Let K = . The objective function in fact becomes K + aS – (c – d). Intuitively, when S is fixed, our goal is to maximize the number of napkins sent to slow laundry.Read full article from Caterer problem | Algorithms Notes
