钢条切割问题 问题背景 现在有一个长度为10的钢条，可以零成本 将其切割成多段长度更小的钢条，我们先要求出最大收益 钢条长度 0 1 2 3 4 5 6 7 8 9 10 价格p 0 1 5 8 9 10 17 17 20 24 24 如果我们不切割的话可以获得的最大收益为 24 如果我们按照 2 2 6 切割方法，收益为 27 所以不同的切割方法收益不同，我们寻求的就是收益最大的切割方法 问题定义 输入： 钢条的长度n 价格表pl(1≤ l ≤n)：表示长度为l的钢条价格 输出： 求得一组切割方法，令收益最大化 问题观察 假设钢条能够至多切割一次：有以下这几种情况 我们就需要从这几种切割情况中寻找出收益最大的，max{p[i] + p[10-i], p[10]} 如果钢条能够切割两次： 我们可以现将钢条切割出一段 然后再剩余的钢条中继续切割 这时候 长度为8的就可以看做切割次数为一 的那一种情况 ​ 这里可能存在最优子结构 和重叠子问题 问题结构分析 问题表示： C[j]:切割长度为j的钢条可得到的最大总收益 递推关系的建立 ...

最长公共子序列问题（动态规划） 给定两个序列X和Y： 其公共序列为： 这里我们要找出它的最长子序列，由上面的情况得出最长的公共自序列长度为4 为BCAB 如果我们采用枚举法的话，有如下这种情况： 我们再次观察一下这个公共自序列： 我们发现长一点的数组依靠于短一点的数组：这时候可能会出现最优子结构 和重叠子问题 当一个结构里面包含最优子结构问题和重叠子问题的时候我们就应该想到使用动态规划来解决这个问题 动态分析问题 我们采用C[i, j] 来表示[1…i]和Y[1…j]的最长公共子序列长度 我们从最后一个字母来开始推导，有两种情况， 情况一： 这两个序列的最后一个字母不相同 如果最后两个字母不同的话，可分为两种情况 情况一 C[i, j] = C[i, j -1 ] + 0 情况二 C[i, j] = C[i-1, j] + 0 情况二： 这两个序列的最后一个字母相同。 这里面需要分为三种情况： 第一种：最后这个相同的字符在最长子序列中 第二种：最后这个相同的字符不一定出现在最长子序列中，我们删除第一个序列的最后一个，在和第二个序列相比较 第三种：最后这 ...

最大公共子数组问题（分治法） 原理： 采用二分法，分别找出左边数组的最大值，右边数组的最大值，再找出带有中间元素的最大值 S1:数组X[1,n/2]中的最大值 S2:数组X[n/2+1, n]的最大值 S3:包含中间元素的最大值 算法实例： 分解： 归并： 代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071'''最大子数组问题（分治法） 这里主要分为三个部分 1.求二分之后左边和右边的最大值 2.求合并之后的最大值 3.上面三者比较取最大值'''def max_sub(X, start, end): # 如果只有一个数字的话那么最大子数组就是它本身 if start == end: return X[start] # 记录一下中间位置 ...

硬币收集问题（动态规划） 问题： （硬币收集问题）在n*m格木板中放置一些硬币，每一个格子上最多放置一个硬币。在木板的左上方，一个机器人需要收集尽可能多的硬币，并把他们带到右下角的单元格。每一步，机器人可以从当前位置向右或向下移动一格，当遇到一个有硬币的单元格时，就会将该硬币收集起来。设计一个算法，找出机器人能够收集到最大硬币数，并给出路径。 因为这里机器人只能向下和右边 走所以matrix[n,j]的位置确定依赖于 上面和左边 代码为： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960''' 收集硬币问题： （硬币收集问题）在n*m格木板中放置一些硬币，每一个格子上最多放置一个硬币。 在木板的左上方，一个机器人需要收集尽可能多的硬币，并把他们带到右下角的单元格。 每一步，机器人可以从当前位置向右或向下移动一格， 当遇到一个有硬币的单元格时，就会将该硬 ...

理解： 线性回归，首相非为两类， 一类是线性模型， 一类是回归问题， 综合起来就是使用线性模型解决回归问题 线性模型和回归问题并不是一开始就被绑在一起的，模型与问题之间是多对多的关系，例如有逻辑模型，分类问题， 只是因为在使用线性模型解决回归问题的时候，发现比较好用，所以才有了“线性回归”这个名词 回归问题 用于预测未来的回归问题： 在回归的世界里，万物的发展轨迹都不是一条单调向上走或向下走的直线，而是循着均值来回波动，一时会坠入低谷，但也会迎来春暖花开，而一时春风得意，也早晚会遇到坎坷挫折，峰回路转，否极泰来，从这个角度看，回归与其说是一个统计学问题，不如说更像是一个哲学问题。 简单来说就是各个数据点都沿着一条主轴来回波动的问题都算是回归问题 记录历史值和预测未来值是回归问题的两个代表特征 回归问题和分类问题的区别 回归问题和分类问题最大的区别是在于预测结果： 根据预测值类型的不同，预测结果可以分为两种，一种是连续的一种是离散的，连续的就是预测问题 下面是连续型数据 下面是离散型数据，离散型数据最大的特征就是缺乏中间过渡值，出现阶级跳跃，譬如“是”和“否”，通常使用boo ...

数据结构排序算法 python实现： 该文章实现了冒泡，快速，选择，插入排序，二分插入排序，希尔排序，堆排序，归并排序，基数排序 冒泡排序 12345678910111213# 冒泡排序def bobble_sort(data): for i in range(len(data) - 1): data_mark = 0 mark = 0 for m in range(1, len(data)-i): if data[data_mark] > data[m]: data[data_mark], data[m] = data[m], data[data_mark] mark = 1 data_mark = m if mark == 0: break return data 快速排序 123456789101112131415161718192021# 快速排序def find_mid( ...

以下是我自己的一些认知，如果有理解不到位的地方还请指正！！谢谢 支持向量机 我们下面主要是围绕这几个问题来展开叙述 我们在使用分类问题的时候，什么样的决策边界才是最好的 如果特征数据本身很难区分，怎么办才好 计算复杂度怎么样？能够实际应用吗 好，下面我们来进行第一个问题的解释： 最优决策边界： 就像上面这张图片，如果我们想要将其分开，我么有以上两种分开的方法，都可以比较好的分开图片，但是支持向量机寻找的就是最优的决策边界，如图所示，比较好的分割这一份数据的边界时LargeMargin 这条线， 由此我们选择决策边界的时候 我们的宗旨是：选择离我们最近的点的最大距离。 数据点到决策边界的距离 我们既然想要求出离我们最近的点的最大距离，第一步我们当然是要求出离我们最近的点， 如图所示，我们想要求出点X到我们决策边界面的最短距离，目的就是求出X到决策面的距离 我们假设这个决策面的方程为 Ax + By + Cz = D，其中(A, B, C)为法向量 m1为平面外一点，m0为平面内一点，则：d = |M0M1|cosα, cosa = (M0M1 * n)/ (|M0M1| ...

聚类算法 聚类的概念： 聚类是一个无监督问题，我们在分类的时候没有哪一类的标签了 聚类：相似的东西分到了一组 难点：如何评估，如何调参 K-MEANS算法 基本概念 要得到簇的个数，需要指定K值，例如上图所示，它的K值就是3 质心：均值，即向量各维度取平均即可，就是各个簇最中心的点 距离的度量：这里有两种方法： 欧氏距离：sqrt[(x1-x2)^2 + (y1-y2)^2 ……] 余弦相似度：以原点为起始点，需要比较的两个点为终止点，做向量，求这两个向量的余弦，余弦约小这两个点越相似 我们一般使用欧氏距离来计算两点的距离 我们在计算的时候应该先吧数据标准化，为了防止不同维度上数据差距，导致的误差，标准化之后，可以让他们变化范围尽可能的缩小，不影响我们计算 要优化的目标： 其中最外层的是从1 到 K 相加， 最里层是每一个类中每一个点到质心的距离 我们想要的是 在每一个类中属于该类的点到该类的质心的距离和最小 工作流程 这是我们的初始数据分布图。现在假设我们把它分为两类 K = 2 当我们确定分完的类数之后，会随机生成 ...

大整数乘法 大整数乘法采用分治法来解决这个问题：先把大整数分为两部分 A和B 例如123456789 = 12345 * 10410^4104 + 6789; 其中x和y不一定都是n为。这样X和Y的乘积： XY = (A * 100.5n10^{0.5n}100.5n + B)(C * 100.5m10^{0.5m}100.5m + D) = A * C * 100.5n+0.5m10^{0.5n + 0.5m}100.5n+0.5m + (AD * 100.5n10^{0.5n}100.5n + CB * 100.5m10^{0.5m}100.5m ) + BD 如果按照上面这个方式计算的话一共需要进行4次乘法最后的时间复杂度还是 2n2^n2n 因此我们还需要进行化简： 我们可以把(AD * 100.5n10^{0.5n}100.5n + CB * 100.5m10^{0.5m}100.5m ) 进行化简: 为了减少递归的次数我们可以将上面式子中的公共部分提取出来方便计算 步骤： 我们先判断一下0.5n 是否大于 0 ...