他的首页
他的馆藏
他的动态
馆友反馈
关于他
| 共 5 篇文章 |
|
01背包 动态规划之01背包问题（最易理解的讲解） 01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。 阅102 转0 评0 公众公开 15-04-09 17:09 |
简单动态规划。根据电路设计，要求用导线（i，π(i)）将上端接线柱i与下端接线柱π(i)相连，如图所示。导线（i，π(i)）称为该电路板上的第i条连线。比较基础的动态规划问题，设a[i][j]为上端接线柱i与下端接线柱j前的最大不相交子集，则：1. 若i与j不相连，则i与j前的最大不相交子集等于i与j - 1前或i - 1与j前的最大不相交子集的最大值，2. ... 阅1 转自dinghj 公众公开 15-04-09 11:08 |
而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。上式的意义是，对于某个阶段k的某个状态xk，从该阶段k到最终目标阶段n的最优指标函数值等于从xk出发取遍所有能策略pkn所得到的最优指标值中最优的一个。使指标函数Vkn达到最优值的策略是从k开始的后部子过程的最优策略，记作pkn*={u... 阅1 转自看风景D人 公众公开 15-04-09 10:53 |
非常重要！，不要认为概念不重要，理解的深刻，你才知道对于什么样的问题去考虑有没有动态规划的方法，以及如何去使用动态规划。如果采用自顶向下的递归来解，那么就避免了不必要子问题的求解（相对于动态规划表现出优势），然而递归又会导致对同一个子问题多次求解（相对于动态规划表现出劣势），所以将递归和动态规划结合起来，就可以设计一... 阅1 转自Home of h... 公众公开 15-04-09 10:10 |
状态找到了，下一步找出状态转移方程。在经典的迪杰斯特拉问题中，我们使用一个一维数组来保存从开始结点到每个结点的最短路径的长度，即M[i]表示从开始结点到结点i的最短路径的长度。在每一步中，对于已经找到的最短路径，我们找到它所能到达的下一个未标记状态(i,j)，将它标记为已访问(之后不再访问这个结点)，并且在能到达这个结点的各个最... 阅1 转自adkada 公众公开 15-04-08 14:13 |
