蝶儿忙求offer

算法

Linux(2) Vue(2) 未归档(2) 网络(1)

/ 注册

全部文章 / 算法（共4篇）

0-1背包问题——回溯法求解

0-1背包问题：物品总数n，每个物品的体积w[i]，价值v[i]，给定背包的总容量W，求放入背包中物品的最大价值。用回溯法对0-1背包问题进行求解，具体思路是： 1.使用解空间进行标记每个物品的放入情况，即要建立一个数组进行保存其是否放入，可使用 bool x[i]进行标识； 2.回溯法第...

回溯法算法

2019-03-19

0 1136

游艇租赁最小代价——动态规划求解

问题：江上有6个游艇站，游客可以从任意一个站租赁游艇，并在其下游任意一个站归还游艇，不同站之间的费用不同。游艇出租站i到j之间的租金为r(i,j)。上下游情况以及各站点之间的费用如下：图片来源于陈小玉老师的《趣学算法》思想：假设i到j经过在k停靠有最优情况，那么，原问题就分解为求解 ...

动态规划算法

2019-03-04

0 653

最长公共子串——动态规划求解

上篇总结了最长公共子序列用动态规划求解的问题，由此也引出了最长公共子串使用动态规划思想求解的问题。再次辨析下两者的关系，最长公共子序列 VS 最长公共子串：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。其实话句话说最长公共子序列中包含着...

动态规划算法

2019-03-01

0 597

最长公共子序列——动态规划求解

问题：例如：X={A,B,C,B,A,D,B}，Y={B,C,B,A,A,C}，那么，二者的最长公共子序列是{B,C,B,A}，长度为4。我们首先需要搞清楚以下两个概念：最长公共子序列 VS 最长公共子串：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并...

动态规划算法

2019-03-01

0 441