动态规划-限定条件求最优解

动态规划-限定条件求最优解

游戏中经常会用到一些buff道具,最常见的比如建造建筑时使用的时间缩短道具,行军加速道具包,血量回复包等。在几种道具中选择最合适的道具包达到目标效果。许多游戏中的解决方法是使用贪心算法,这种只是一般可行解,并不被玩家接受。用动态规划算法可以构造出最优解。

动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划

我们先来构造一般意义上的最优解

假设当前我们在建造一个建筑,建筑需花费n小时的时间,玩家拥有3种道具a、b、c,分别能使建筑时间缩短1、2、3小时,我们来看看每个阶段的最优解情况

我们来解释下表格所表达的意思,一般的我们认为在所有道具都参与的情况下的解决方案为最优解,并且优先使用时效长的道具
image
当目标为缩短1小时的时候的最有解,结果为使用 1个道具a。同理,目标为2时使用一个b,目标为3时使用一个道具3。观察3中的第二列解image ,意思为当目标为缩短3个小时时,在拥有道具a和b情况下的最有解。至此,大家应该明白表格所表达的意思了吧。

现在,我们对道具数量做出限定,假定在b、c只有一个的情况下,求6小时的最优解。我们继续构造最优解表格

表格理解应该是没有难度了,现在我们来分析下如何用代码实现。。。 这边贴代码太难看了,还是去我的公众号看吧
https://mp.weixin.qq.com/s/XwSkAHbiNoYxcc8KEVw6yQ

1赞