最近发现自己在算法的方面真的是犹如小学生一般,跟公司的从一些更厉害学校毕业的人都不在一个水平面上,唉,觉得以前大学期间真心是一个学渣,虽然软件工程方面还可以,但是时候该补一补关于算法的相关知识了。
学习算法的同时,也顺带着学习python脚本语言。
动态规划
动态规划是通过组合子问题的解来解决整个问题的,通过将问题分解成多个相互不独立的子问题,例如0/1背包问题,对每个子问题求解一次,并将其结果保存到一张辅助表中,避免每次遇到各个子问题时再重新计算,动态规划通常用于解决最优化问题。
(1)全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解 ;
(2)动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解 ;
(3)边界条件:即最简单的,可以直接得出的局部最优解。
有n件物品,第i件物品价值为vi元,重量为wi,假设vi和wi都为整数,希望带走的东西越值钱越好,但他的背包中之多只能装下W磅的东西,W为一整数。问题是应该带走哪几样东西?
0/1背包问题是一个典型的最优子结构的问题,只能采用动态规划来解决,不能采用贪心算法。
class Commodity: def __init__(self, value, weight): self.__value = value self.__weight = weight def get_value(self): return self.__value def get_weight(self): return self.__weight if __name__ == '__main__': totalCount = 3 bagCapacity = 50 commodities = [Commodity(0, 0), Commodity(60, 10), Commodity(100, 20), Commodity(120, 30)] matrix = [[0 for i in range(bagCapacity + 1)] for i in range(totalCount + 1)] # initial set value = 0 when commodity count = 0 for i in range(1, bagCapacity + 1): matrix[0][bagCapacity] = 0 for i in range(1, totalCount + 1): # set max value = 0 when capacity = 0 matrix[i][0] = 0 for w in range(1, bagCapacity + 1): if ( commodities[i].get_weight() <= w): if (commodities[i].get_value() + matrix[i - 1][w - commodities[i].get_weight()] > matrix[i - 1][w]): matrix[i][w] = commodities[i].get_value() + matrix[i - 1][w - commodities[i].get_weight()] else: matrix[i][w] = matrix[i - 1][w] else: matrix[i][w] = matrix[i - 1][w] print "The max value matrix is : %s" % matrix remaining_space = bagCapacity # we should output selected commodity for i in range(totalCount, 0, -1): if(remaining_space >= commodities[i].get_weight()): if(matrix[i][remaining_space] - matrix[i-1][remaining_space-commodities[i].get_weight()] == commodities[i].get_value()): print "item %s selected" % i remaining_space -= commodities[i].get_weight()
首先,我们定义了一个Commodify类来描述物品的二维特性,价值和重量。
第一步,逐步建立局部最优解的状态矩阵,状态矩阵表示,在一定数量内的物品,一定范围的总重量范围内的最大价值是多少?
我们最简单的边界条件设置为,当有0个物品时,最大价值必定为0;当物品的总重量为0时,最大价值也必然为0;
第二步,当我们选定一个物品,如何判断是否应该加入最优解的结果中呢?首先判断这个物品是否大于局部最优解限定的重量,如果大于直接pass掉,使用上一步骤的局部最优解。
如果在限定的重量范围内,并且加上这个物品的要比不加这个物品的局部最优解要大,也就是说质量不变的情况下,能否用更多数量的物品达到更大价值,那么这是最新的最优解;否则仍然选择上一步骤的局部最优解,判断条件为:
if (commodities[i].get_value() + matrix[i - 1][w - commodities[i].get_weight()] > matrix[i - 1][w]):
最后,我们建立起这个矩阵,最后面的matrix[totalCount+1][bagCapacity+1]就是最终的最优解。
那么需要列出在此过程中,我们选择了哪些物品,从局部最优矩阵的结果入手,向前递推,如果遍历的这个物品的最优解减掉该物品的重量刚好差值为该物品的质量,那么证明刚才的最优解中选择了该物品。
if(matrix[i][remaining_space] - matrix[i-1][remaining_space-commodities[i].get_weight()] == commodities[i].get_value()): print "item %s selected" % i remaining_space -= commodities[i].get_weight()
相关推荐
ACM程序设计,动态规划的课件,相关练习,以及各种题型,由简单到复杂,由容易到困难的各个阶段。是学习这一基本算法的很好的辅助资料。
在学习动态规划之前,先得对下面的名词有所了解。本书将标准名词作了一些简化,便于大家更好的理解。 (1)状态(smte) 对于一个问题,所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个状态。 (2)...
帮助了解动态规划算法
学习动态规划算法
第四章动态规划2020年10月26日星期一学习要点理解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构性质(2)重叠子问题理解动态规划算法与贪心算
【达摩老生出品,必属...资源名:matlab实现动态规划算法 程序源码.zip 资源类型:程序源代码 源码说明: 基于matlab实现动态规划的程序,包含完整源码和注释,非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
动态规划学习笔记 // /经典问题/状态表示/状态转移方程 https://blog.csdn.net/weixin_37863080/article/details/103261838 和上文配套使用更佳
这里是对动态规划法的介绍,是专门学习了算法设计与分析这本书后收藏的ppt,如果大家需要可以下载看看
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
AOVAOE网络 动态规划算法PPT学习教案.pptx
算法分析与设计中的第三章节,动态规划。里面都是PPT的格式,方便你们学习
第7章 动态规划法学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。理解动态规划算
摘要视图订阅登录 | 注册195897次第4587名57篇33篇0篇117条0020算法笔记——【动态规划】最优二叉搜索树问题 liufeng_king的专
局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法,算法引入了随机因素,不一定能找到最优解,但一般能快速找到满意的解
基于MATLAB实现的机器人Q-Learning路径规划算法动态仿真设置起点和终点 动态图形显示 运行PathPlanning代码后,图形GUI界面设置起点和终点,还可以设置障碍,然后开始路径规划,可以动态绘制路线,最终从起点到达...
算法与设计动态规划法PPT学习教案.pptx
动态规划和贪心算法区别,供大家学习,如有毛病,还大神望误喷。
NULL 博文链接:https://128kj.iteye.com/blog/1691677
基于nedc工况的动态规划算法对汽车换档规律进行优化 代码可以在matlab中正常运行 价值非常高,不懂的可以留言学习