支持向量机 (线性不可分情况) 发表于 2022-01-26 上节回顾线性可分情况下，支持向量机寻找最佳超平面的优化问题可以表示为： 线性不可分情况如果训练样本集是线性不可分的，那么以上优化问题的解，是什么呢？ 在稍微思考下，以上的问题，是没有解的。 即：不存在 $ \omega \ 和 \ b$ 满足上面所有的 $ N $ 个限制条件。 对于线性不可分的情况，我们要适当的放松限制条件。使上面的最优化问题变得有解。 阅读全文 »
0-1背包问题-动态规划 发表于 2021-12-30 更新于 2022-01-04 分类于 数据结构与算法 0-1背包问题-动态规划一、问题描述 给定n种物品和一个背包。物品i 的重量是 w_i ，其价值是v_i ，背包的容量为c 。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ 阅读全文 »
活动安排问题-贪心思想 发表于 2021-12-29 更新于 2022-01-05 分类于 数据结构与算法 活动安排问题-贪心一、贪心贪心算法是通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下的最好选择，即贪心选择。 即希望通过问题的局部最优解来求出整个问题的最优解。 阅读全文 »
查找第K小问题-分治思想 发表于 2021-12-29 更新于 2022-01-05 分类于 数据结构与算法 查找第K小问题-分治选择问题（select problem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。 当k=1时，是求最小元素；而当k=n时，就是求最大元素；当k=(n+1)/2时，称为中位数。 阅读全文 »
最长公共子序列问题-动态规划 发表于 2021-12-29 更新于 2022-01-05 分类于 数据结构与算法 最长公共子序列问题-动态规划一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X={x1,x2,…,xm}，则另一序列Z={z1, z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1, i2,…, ik}使得对于所有j=1,2,…, k，有: zj=xij。例如，序列Z={B,C, D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。 给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 阅读全文 »
