Skip to content

baseMind

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History
 
 

baseMind

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
dynOneZero.go
dynOneZero.go
 
 
eightQueens.go
eightQueens.go
 
 
example.go
example.go
 
 
oneZoreBag.go
oneZoreBag.go
 
 

README.md

四种基本算法思想

  1. 贪心算法
    • 基本应用
      • huffman压缩算法
    • 使用场景：在多个权重不同的物品中选择期望值最大的组合
    • 使用步骤
      • 看是否符合场景
      • 用推理假设一下
      • 是否是最优解要看前后连个物品或者事件是否有联系，有联系的情况下可能不是最优解
    • 例子
      1. 分糖果：m个糖果,n个小朋友 m<n，使最多的孩子满足期望
      2. 找了零钱：K 元，不同面值，用最少的数量支付金额
      3. 区间覆盖：n个区间，如何选择最多的不相交的区间，左端从小到大排序，遍历左端，找右端最小的，可以又更多的覆盖区间
    • huffman编码
      1. 先统计包含不同字符的数量，根据数量不同用二进制进行重新编码
      2. 不仅统计数量还统计频率，按照频率做不同长度的编码，最后进行重新编码
  2. 分治算法
    • 基本应用
      • mapReduce
    • 使用场景：原问题和分解后的问题有相同的处理模式，子问题之间没有联系，问题有终止条件，并且能最终合并成原始问题。
    • 使用步骤
      • 分解问题
      • 解决问题
      • 合并问题
    • 例子
      1. 求数组的逆序度：利用归并算法进行计算。
  3. 回溯算法
    • 基本应用：深度优先算法，正则匹配，编译原理的语法分析，数独，0-1背包，图着色，旅行商等等
    • 使用场景：在选择中搜索最优解，分阶段最优解。
    • 使用步骤：
      1. 拆分情况
      2. 选择情况
      3. 回溯检查
    • 例子
      1. 皇8
      2. 数独
      3. 0-1 背包
      4. 正则匹配
  4. 动态规划
    • 基本应用：0-1背包
    • 使用场景：在选择中搜索最优解，分阶段最优解，最小值，最大值。
    • 使用步骤
      1. 拆分情况
      2. 分析是否有重复的拆分情况
      3. 使用方法减少充分情况
    • 列子
      1. 0-1背包问题
      2. 双十一拼单
    • 理论讲解
      1. 模型：多阶段决策最优模型
      2. 三个特征
        • 最优子结构
        • 无后效性
        • 重复子问题
      3. 解决思路
        • 状态转移表法
        • 状态转移方程式