对动态规划中一系列问题的深刻理解(11)
动态规划的本质问题基本如前所述，前面的问题相对简单。复杂动态规划问题有几种表现形式，其中一种是代价函数的计算比较复杂，在状态转移过程中需要考虑更多细节。今天这个问题符合这个条件：DPP问题()
问题如下：假设有一个湖，湖里有一些鱼，第一年有b1鱼，然后第一年有bt鱼。渔民以捕鱼和卖鱼为生。如果他们第一年卖xt鱼，可以赚r(xt)。当然，捕捉这些鱼也会造成c(xt，bt)的成本。鱼每年自然繁殖，假设繁殖规律固定，每年以s的比例自然生长。同样，渔民手里的钱都存银行，每年都会有固定的利息。想问一下从第一年到t年，每年都是怎么捕鱼，利益最大化？你不能筋疲力尽地钓鱼，当然也不能等着饿死。
这个描述乍一看，说明目标很明确：——使收益最大化，但是条件n很多，在求解DP时，要仔细考虑状态转移方程中的核心优化条件。首先我们定义状态，年份T是自然维度。要知道收益，已知的条件包括利润函数、成本函数、增长率和固定利息。共同需求是鱼B的数量，所以状态是(t，B)。因为T在1和T之间(这本身也是递归收敛条件)，所以DPFE方程是分段方程：f(t，b)=0当且仅当tT具体解释一下，我们在计算T年B鱼的收益时，假设xt鱼被捕捞，那么收益相当于鱼销售收入r(xt)减去捕捞成本c(xt，B)，再加上下一年的收益和利息。
看似复杂的问题，其实核心状态明确后，逻辑就明确了，虽然条件很多，但复杂度只是在目标计算中增加。这样的问题对于DP来说并不太复杂。
作为一个实际例子，我们假设T=2，y=0.05，s=2，初始b1=10(单位为千)，效益函数也线性化为3xt，成本函数简化为2xt，那么我们实际上是在找f(1，10)，答案输出是其优化决策为x1=0，x2=20，即第一年。)
源代码：
相关阅读
标签： #动态规划最新问题
