动态规划算法设计——实例2

2021/5/4 12:55:21

本文主要是介绍动态规划算法设计——实例2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

动态规划算法设计——实例2

今天继续做题!

题目大意

  • 有n个货柜。货柜的宽度和仓库的宽度是一致的,所以我们需要考虑货柜的长度,每个货柜的的长度用 l i l_i li​来表示。设仓库的总长度为D。每个货柜的收益是 v i v_i vi​。问如何选择放入库房的货柜,使得仓库的收益得到最大。
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SefLYzlH-1620101520714)(动态规划算法设计——实例2.assets/question.jpg)]

题目思路

  • 有了昨天实例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​。

伪代码

]



这篇关于动态规划算法设计——实例2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程