动态规划算法设计——实例2
今天继续做题！
题目大意
- 有n个货柜。货柜的宽度和仓库的宽度是一致的，所以我们需要考虑货柜的长度，每个货柜的的长度用
l
i
l_i
li来表示。设仓库的总长度为D。每个货柜的收益是
v
i
v_i
vi。问如何选择放入库房的货柜，使得仓库的收益得到最大。
题目思路
-
有了昨天实例1的经验，我们一定要把这些题目往那些经典的题目上靠，比如这道题，和01背包问题其实是一样的，01背包中每个物品只能选择依次，而这个货柜每种只有一个。01背包中的限制是背包大小，而这道题里只是把限制改为了仓库的长度。
-
所以我们选择两个规模参数，一个是k，表示在前k个柜子中进行选择，一个是y，表示仓库长度限制为y。我们可以很容易的写出递推方程。
-
F k ( y ) = m a x { F k − 1 ( y ) , F k ( y − l k ) + v k } F_k(y) = max\{F_{k-1}(y),\ F_k(y-l_k)+v_k\} Fk(y)=max{Fk−1(y), Fk(y−lk)+vk}
-
这里还需要注意当 y < l l y < l_l y<ll时， F k ( y ) F_k(y) Fk(y)将直接等于 F k − 1 ( y ) F_{k-1}(y) Fk−1(y)
-
然后是优化函数的初值，也就是只选择第一个柜子的时候，因为第一种柜子只有一个。
-
所以 F 1 ( y ) F_1(y) F1(y)在 y < l k y<l_k y<lk的时候将是0，因为一个柜子也放不下，收益是0。当 y ≥ l k y\geq l_k y≥lk时，放得下第一个柜子，所以收益是 v i v_i vi。