基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

0-1背包问题之穷举、搜索、动态规划算法探讨

该文论述了算法学习中非常经典的0-1背包问题,探讨用穷举、搜索、动态规划三种算法来解决0-1背包问题,并讨论算法在时间和空间复杂度上的优化,给出具体的参考程序。     

背包问题的量子计算算法

背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O（n²）。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O（√N/M）步完成对规模为n的背包问题求解（M是解的数目）,而基于原始Grover算法的背包问题量子计算算法计算复杂度为O（√N/M）,成功率是50%～100%。     

0-1背包问题 动态规划和回溯法的比较

动态规划算法是特待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解．而田溯法是从开始结点(根结点)出发，以深度优先的方式搜索整个解空间．获取于0-1背包问题的最优解通常有动态规划算法和回溯法，本文着力比较这两种算法的复杂度和适用场合。     

贪心核加速动态规划算法求解折扣{0-1}背包问题

针对现有动态规划算法求解折扣{0-1}背包问题（D{0-1}KP）缓慢的问题，基于动态规划思想并结合新型贪心修复优化算法（NGROA）与核算法，通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划（GCADP）算法。首先利用NGROA对问题进行贪心求解，得到非完整项；然后通过计算得到模糊核区间的半径和模糊核区间范围；最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划（BDP）算法求解。实验结果表明：GCADP算法适用于求解D{0-1}KP，且在求解速度上相比BDP算法平均提升了76.24%，相比FirEGA算法平均提升了75.07%。     

面向异构多背包问题的多级二进制帝国竞争算法

在传统多背包问题的基础上，从典型物流服务场景中共性抽象出异构多背包问题（HMKP），并设计和定制了一种帝国竞争算法（ICA）对HMKP进行求解和评估。针对原始ICA易陷入局部最优以及0-1背包问题最优解往往在约束边界周围的特点，设计了双点自变异策略（TPAS）和跳出局部最优算法（JLOA）对ICA进行改进，提出面向0-1背包问题的二进制帝国竞争算法（BICA）。BICA在求解35个0-1背包问题算例时展现出了全面、高效的寻优能力，基于最佳匹配值法（BMV）的BICA在第一组测试集的20个算例上能对19个算例100%找到理想最优值，在第二组测试集的15个算例上能对12个算例100%找到理想最优值，在所有对比算法中表现最优。数值结果分析表明，BICA在寻优演化中维持多极发展策略，并依托独特的种群进化方式在解空间中高效搜索理想解。在此基础上，针对HMKP强约束性和高复杂度的特性，基于BICA设计了求解HMKP的多级二进制帝国竞争算法（MLB-ICA）。分别在多个典型0-1背包问题算例组合构建的HMKP高维测试集上进行了MLB-ICA的数值实验和性能评估，结果表明虽然MLB-ICA的求解时间比...     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

用动态规划法求解0-1背包问题

0-1背包问题是算法分析中的著名问题,有重要的使用价值,是算法研究的热点。目前较成熟的常用算法有贪心算法、动态规划、回溯法、分枝-限界法等。本文主要通过动态规划原理来求解0-1背包问题。     

基于动态状态树的回溯算法

介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用.     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

Dijkstra算法在停车诱导系统中的应用

路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径.传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O（n2）,存在搜索速度慢和浪费空间的缺点.为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O（nlog2n）.用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径.     

挖掘数据流近似频繁项的改进算法

数据流的无限性、连续性和速度快等特点,使得挖掘出所有准确的数据流频繁项通常是不可能的.算法的空间复杂度和时间复杂度通常是评价频繁项挖掘算法优劣的两个主要度量.通过引入局部性原理改进数据流近似频繁项的挖掘算法,该算法的空间复杂性为O（1/ε）,数据流每个数据项的最坏处理时间是O（1/ε）,其最好处理时间是O（1）,输出结果的频率值误差为∑_(i=2)^j（1-μ_i）×k_i。     

一种新的基于哈希函数的排序算法

提出一种哈希函数分档的排序算法。根据数组下标递增的特点,针对任意分布整数,建立有效的哈希函数,通过反复映射完成排序。分析算法的时间和空间复杂度,实验验证算法的运行效率。算法分析和实验结果表明：算法的时间和空间复杂度均为O（n）,在问题规模较大时,效率优势明显。     

Dynamic Programming Revisited: Improving Knapsack Algorithms

The contribution of this paper is twofold: At first an improved dynamic programming algorithm for the bounded knapsack problem is given. It decreases the running time for an instance with n items and capacity c from to , which is the same pseudopolynomial complexity as usually given for the 0--1 knapsack problem. In the second part a general approach based on dynamic programming is presented to reduce the storage requirements for combinatorial optimization problems where it is computationally more expensive to compute the explicit solution structure than the optimal solution value. Among other applications of this scheme it is shown that the 0--1 knapsack problem as well as the bounded knapsack problem can be solved in time and space. Received: October 15, 1998; revised March 10, 1999     

解决0-1背包问题的遗传分布估计算法

0-1背包问题是典型的NP难问题,针对0-1背包问题提出分布估计算法（EDA）与遗传算法（GA）相结合的算法（E-GA）。该算法在每一次迭代中由二者共同产生种群,并行搜索,两种方法产生的个体数目动态变化,将EDA的全局搜索与GA的局部搜索能力、EDA的快速收敛性与GA的种群多样性结合,实现优势互补。通过三个背包问题算例进行算法验证,与以往文献相比,结果显示该算法所获最优值优于文献最优值,运行时间短且收敛速度快。