Algorithm

动态规划 – 01背包问题

谈论动态规划,就需要提及另一个算法:贪心算法。 某些现实中的问题可以采取贪心思路来解决:局部最优,最终达到全局最优。计算出结果。 然而不幸的是,不是所有的问题都有局部最优就能得到全局最优的特性。解决思路比NP完全问题的处理稍微好受一点。通过将问题拆分成子问题,逐个解决。它有局部最优的特性,但是相比贪心算法考虑的更多,下面就说说这类解决方案:动态规划。 在动态规划的领域,比较经典的问题就是01背包。它的场景是这样的:游戏主人公有一个容量有限的背包,他有一些可供选择的物品。每一件物品都有自己的价值与所占空间。问,背包可以装下物品的最大价值是多少? 假设背包的容量是V。 那么我们通常需要考虑V – x 和 x的背包情况,比较两者之和 与 容量为V的结果。 每一个物体有两种使用情况:装到背包里,不装到背包里。 所以,思考的维度是2。我们得到了一张表格。 1(Volumn) 2 3 4 5 value1 value2 表格的列表示容量,行表示物品(决定需要还是不需要)。 例子 杭州电子科技大学在线测试问题: http://acm.hdu.edu.cn/showproblem.php?pid=2602 5 10 1 2 3 4 5 5 4 3 Read more…

By theArcticOcean, ago
Algorithm

Dijkstra Algorithm

本文内容学习自 Aditya Bhargava 的《算法图解》 图论领域中的狄克斯特拉算法包含4个步骤。 (1) 找出最便宜的节点,即可在最短时间内前往的节点。 (2) 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销。 (3) 重复这个过程,直到对图中的每个节点都这样做了。 (4) 计算最终路径。 要计算非加权图中的最短路径,可使用广度优先搜索。要计算加权图中的最短路径,可使用狄克斯特拉算法。 在无向图中,每条边都是一个环。狄克斯特拉算法只适用于有向无环无负权边的图。 狄克斯特拉算法这样假设:对于处理过的海报节点,没有前往该节点的更短路径。这种假设仅在没有负权边时才成立。因此,不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中,要找出最短路径,可使用另一种算法——贝尔曼-福德算法(Bellman-Ford) youtube video python code: #!/usr/local/bin/python3 # -*- coding: UTF-8 -*- graph = {} graph["start"] = {} graph["start"]["A"] = 6 Read more…

By theArcticOcean, ago
Algorithm

【Algorithm】分而治之

分而治之算法是递归的。使用分而治之解决问题的过程包括两个步骤。 (1) 找出基线条件,这种条件必须尽可能简单。 (2) 不断将问题分解(或者说缩小规模),直到符合基线条件。 能够不断缩小问题的规模,并且有终止的条件是分而治之的核心。在这样的方案构建过程中,归纳证明非常重要。 练习1、使用递归分而治之的方法计算2,4,6的和。 本图来自《算法图解》 def Sum( array ): if( 0 == len(array) ): return 0 if( 1 == len(array) ): return array[0] firstOne = array.pop( 0 ) return firstOne + Sum( Read more…

By theArcticOcean, ago
Algorithm

【Algorithm】基础算法之排序、递归、二分查找

选择排序 选择排序是一种简单、低效的排序方法。 他每次都从序列中按顺序搜索寻找最值,所以总的查找次数为n,n-1, n-2, n-3, ……, 1 大O表示法:O(n^2) 注意:大O表示法忽略常数1/2. def findSmallest( arr ): smallest_index = 0 for i in range(1, len(arr)): if( arr[i] < arr[smallest_index] ): smallest_index = i return smallest_index def selectSort( arr ): Read more…

By theArcticOcean, ago