| 共 3 篇文章 |
|
动态规划之背包问题（一）动态规划之背包问题（一） March 1, 2013 作者：Hawstein出处：http://hawstein.com/posts/dp-knapsack.html声明：本文采用以下协议进行授权： 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ，转载请注明作者及出处。如果我们把2号宝石放入了背包，那么是不是也就意味着，前3个宝石放入背包的最大... 阅12871 转68 评0 公众公开 13-06-01 01:22 |
状态找到了，下一步找出状态转移方程。在经典的迪杰斯特拉问题中，我们使用一个一维数组来保存从开始结点到每个结点的最短路径的长度，即M[i]表示从开始结点到结点i的最短路径的长度。在每一步中，对于已经找到的最短路径，我们找到它所能到达的下一个未标记状态(i,j)，将它标记为已访问(之后不再访问这个结点)，并且在能到达这个结点的各个最... 阅224854 转932 评8 公众公开 13-06-01 00:54 |
