

$10.$餐巾计划问题

题目

一个餐厅在相继的 $N$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾($ i=1,2,...,N$)。餐厅可以购买新的餐巾,每块餐巾的费用为 $p$ 分 ;或者把旧餐巾送到快洗部,洗一块需 $m$ 天,其费用为 $f$ 分;或者送到慢洗部,洗一块需 $n$ 天( $n>m$ ),其费用为 s 分( $s<f$ )。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $N$ 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

题解

这题看到有位博主的总结写的不错，就直接贴上来了。 这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。 每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。 在每一天的餐巾需求为 $r_i$ 的情况下，如果满足，必定余下 $r_i$ 个餐巾可以任意处置，所以我们新增流而不是将已经用的流流回。 把每天分为二分图两个集合中的顶点 $X_i$，$Y_i$，建立附加源 $s$ 汇 $t$。

从 $s$ 向每个 $X_i$ 连一条容量为 $r_i$，费用为 $0$ 的有向边。表示每天用完的餐巾 从每个 $Y_i$ 向 $t$ 连一条容量为 $r_i$，费用为 $0$ 的有向边。表示每天必须满足的需求 从 $s$ 向每个 $Y_i$ 连一条容量为 $\infty$，费用为 $p$ 的有向边。表示购买餐巾。 从每个 $X_i$ 向 $X_i+1(i+1\le N)$ 连一条容量为 $\infty$，费用为 $0$ 的有向边。表示餐巾，是可以放着不洗存到下一天的。 从每个 $X_i$ 向 $Y_i+m(i+m\le N)$ 连一条容量为 $\infty$，费用为 $f$ 的有向边。表示快洗。 从每个 $X_i$ 向 $Y_i+n(i+n\le N)$ 连一条容量为 $\infty$，费用为 $s$ 的有向边。表示慢洗。 此图最小费用最大流即为答案。

总结：本题反映了分析一类问题的方法，分析问题的约束条件，分析问题的所有可能决策，从而有的放矢的建图。边，有时候意味着一种决策，我们利用网络流，来获得最优决策。新增流的手法也是很重要。