动态规划算法设计——实例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​。

伪代码