标签：: 数据结构与算法

2016

【动态规划】从子集和问题到背包问题

一、问题定义有一个包含n个元素{e1, e2, ..., en}的集合S，每个元素ei都有一个对应的权值wi。现在有一个界限W，我们希望从S中选择出部分元素，使得这些元素的权值之和在不超过W的情况下达到最大，这个便是子集合问题（事实上还有其他类型的子集和问题，本文暂不讨论）。举个更具体一点的例子，某农民今年收成小番茄总重量为W万斤，有n个采购商想要向这位农民收购小番茄，他们想要采购的数目都有所不同

【动态规划】带权值区间调度问题

一、问题定义存在单一资源R，有n个需求{1, 2, ..., n}，每个需求指定一个开始时间bi与一个结束时间ei，在时间区间[bi, ei]内该需求想要占用资源R，资源R一旦被占用则无法被其他需求利用。每个需求i带有一个权值vi，代表该需求被满足之后能够带来的价值或者贡献。如果两个需求的时间区间不重叠，那么它们是相容的。带权值的区间调度问题即，对上面所描述的情境，求出一组相容子集S使得S中的区间

稳定匹配问题与GS算法-单身狗脱单秘籍

稳定匹配问题稳定匹配问题(stable matching)是一个常见的问题，GS算法是解决稳定匹配问题的一个优秀的算法。下面，我将以男女配对的例子来介绍稳定匹配问题并阐述GS算法的具体步骤。GS算法，全称Gale-Shapley算法。学习完稳定匹配问题和整个算法流程之后，我觉得它还可以起另外一个别名，Get-rid-of-Single算法，单身狗脱单算法。问题描述有n只男性单身狗的集合M = {m

【分治策略】逆序对问题总结

一、逆序对1. 问题背景假如有一组电影集合，包括n部电影。某个人对这n部电影的喜欢程度各有高低，根据其喜欢程度对这n部电影进行排名，按照从1到n的方式进行标记，这就形成了一个关于电影的排名表。假设你和一个陌生人各有自己对于这n部电影的排名表。现在想要比较你跟这个陌生人的“品味”差别，看看你们俩是否有“类似”的爱好。一个很自然的办法就是对比两个人各自的排名表，看看两个排名表的排名状况是否相似。如果两

【分治策略】归并排序算法总结

归并排序思想归并排序的思想很简单，拿到一个无序的序列，先从序列的中间位置将其切分成两个子序列，然后对两个子序列递归地进行归并排序，最后，将排好序的子序列合并成一个完整的有序序列。归并排序算法的伪代码如下：123456序列seq = [s1, s1, s3, ..., sn]归并排序： 将seq切分成两个部分seq1, seq2; 对seq1进行归并排序; 对seq2进行归并排序; 把seq

【贪心算法】Huffman编码

问题描述有一组字符集{c1, c2, ..., cn}，在使用这组字符集的过程中，通过统计发现每个字符都有其相应的出现频率，假设对应的频率为{f1, f2, ..., fn}。现在需要对这些字符进行二进制编码，我们希望的编码结果如下：每个字符都有其独一无二的编码；编码长度是变长的，频率大的字符使用更少的二进制位进行编码，频率小的字符则使用比较多的二进制位进行编码，使得最终的平均编码长度达到最短；每

【贪心算法】Kruskal算法的实现与应用

问题背景假设我们有n个位置的集合V={v1, v2, ..., vn}，我们想在它们顶部建立一个通信网络，网络应该是连通的，即任何两个位置vi和vj之间至少存在一条路径可以相互到达。对于确定的两个位置(vi,vj)，假设在这两个位置之间建立网络连接的费用为c(i,j)，c(i,j) > 0。将上述问题抽象成一个无向图G=(V,E)，用图来表示可能被建立的链接的集合，图的每个结点代表每个位置，

【贪心算法】区间调度问题总结

1. 单区间调度问题问题定义：存在单一资源，有一组以时间区间形式表示的资源请求reqs={req-1, req-2, ..., req-n}，第i个请求希望占用资源一段时间来完成某些任务，这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠，则说这两个请求是相容的，求出这组请求的最大相容子集(最优子集)。举个例子：有一间多媒体课室，某一个周末有多