动态规划的问题

2019-05-21 本文已影响0人最困惑的时候就是能成长的时候

一.基本的解题思路

首先要求,子问题的性质和原问题相同,不论降低某个维度的条件数量,都属于子问题,且子问题的性质和原问题相同,例如背包问题,无论是降低背包的重量还是降低放入背包的物品种类都属于降低维度,但是其维度降低后的问题性质是没有发生改变的

1.建模

①解:一般是一个一维向量例如背包问题中的每种物品的放入数量<x1,x2....xn>
②目标函数:根据不同的问题规约成不同的目标函数例如背包问题是 $max \Sigma ^n _{i=1}vixi$
③约束条件,就是一个问题的限制条件,例如背包为题就是 $\Sigma^n_{i=1}wixi<=b$

2.子问题优化

子问题在相同性质的情况下,对子问题进行处理然后得到最终的解
例如背包问题可以简化为 k为物品数,y为总重量.
当k=m,y=b时就是原问题
⑴: $如果k>0,y>0,且w_k<y$
$F_k(y)代表了k中物品放入总重量为y的背包的最大价值$
如果放入第k种物品,那么最大价值需要从 $F_k(y-w_k)+v_k与F_{k-1}(y)中挑选$
⑵ $当k=0或者y=0时F_k(y)=0$
⑶ $w_k>y, F_{k-1}(y)$
⑷ $如果F_1(y)时,w_1>y,那么F_1(y)=-∞$

然后规约出算式:
$F_k(y) \begin{cases} max\{ F_{k-1}(y),F_k(y-w_k)+v_k \}, &y>vk,k>0,y>0;\\ 0, &k=0或y=0;\\ F_{k-1}(y),&y<w_k;\\ -∞,&k=1,y<w_1 \end{cases}$

二.具体题目

1.零钱兑换

动态规划的问题

一.基本的解题思路

1.建模

2.子问题优化

二.具体题目

猜你喜欢

热点阅读