关于0-1背包问题的算法研究

0/1背包问题是计算机算法中一个经典问题.目前,贪心算法、动态算法和蚁群算法是求解0/1背包问题的主要算法,从各种算法设计思想入手,并进行理论分析.着重讲述一种群体智能算法中的蚁群算法,对解决背包问题的高效性.     

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

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

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

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

求解01背包问题的贪婪蛙跳算法

背包问题是经典的组合优化问题,被广泛应用于生活中的多个领域,如货物装载、预算控制、资源分配和资产管理等。因此,长期以来许多科学家在该领域不断钻研,并取得了丰硕的成果。尽管01背包问题已被研究多年,但由于该问题已被证明为NP完全问题,因此找到最优解并不容易。近年来,大量的智能算法不断被提出并被用来求解01背包问题,如化学反应优化算法、遗传算法、粒子群算法、蛙跳算法、人工蜂群算法、爬山算法和模拟退火算法等。通过对智能算法和01背包问题的探索,文中提出了贪婪蛙跳算法(GFLA)来解决01背包问题。不同于传统的蛙跳算法,GFLA总会在每次模因搜索过程中更新全局最优解,以便在接下来的全局搜索过程使用最新的全局最优解进行搜索,从而扩大解的搜索空间。除了蛙跳算法这类传统的局部搜索和全局搜索策略之外,针对01背包问题,在计算适应度值的阶段,本工作提出了贪心策略并分别将其应用于drop和add两个步骤。在drop阶段,若背包超重,则将其中价值密度最小的物品移出并更新解决方案。在add阶段,若背包还有承载物品的能力,则将未放入背包的重量最小的物品放入背包,并对背包信息进行更新。这样,便大大提高了利用蛙跳算法来求解01背包问题的能力。将贪婪蛙跳算法与蜂群算法、化学反应优化算法、遗传算法和量子演化算法进行对比,结果显示,贪婪蛙跳算法取得了最好的结果,从而表明了该算法是求解01背包问题的有效算法。     

求解0/1背包问题的萤火虫算法

该文将萤火虫算法应用于求解小规模0/1背包问题,利用基本萤火虫算法的求解思想,对0/1背包问题进行分析,通过对物品数为10、25和50的背包问题进行了仿真实验,实验结果表明该算法在解决小规模0/1背包问题是可行的。     

一种新的背包加强算法

背包问题是著名的NP问题,因此它一度成为密码学界的研究热点.由最初的Merkle-Hellman背包算法到后来的Chor-Rivest背包算法,但很多算法都相继被破译.本文提出了一种加强背包算法,具有操作简易性和较强的安全性,可以运用于网络通信加密系统.     

背包问题的量子计算算法

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

基于群体智能的0/1背包问题求解研究进展

0/1背包问题是运筹学中一个经典组合优化NP问题。在简要介绍0/1背包问题基础上,分析展望了0/1背包问题的应用前景。结合已有研究成果,总结并详细分析了蚁群算法、微粒群算法等群体智能算法在0/1背包问题求解方面具有的较好收敛速度、健壮性、稳定性、算法简单等优点。最后,针对群体智能算法在求解0/1背包问题过程中所出现的缺陷,提出了群体智能算法在0/1背包问题求解需要进一步解决的几个问题。     

可重复性背包问题的探讨

可重复性背包问题是每种物品相当于有无限多件,背包中既可装同一种物品,亦可装不同物品,只要保证包中物品价值最大就行.对于3种背包问题,其中有的问题用贪心算法来解决还是比较简单的,而01背包和可重复性背包就需用动态规划算法来实现.     

求解广义背包问题的贪心DS_BPSO算法

首先针对演化算法求解背包问题定义了贪心变换的概念,并给出了该变换的一种有效实现算法;然后将此算法与文献[5]中提出的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)相结合,提出了一种解决广义背包问题GKP(General Knapsack Problem)的快速算法:基于贪心变换的DS_BPSO算法(GDS_BPSO).利用该算法求解文献[3,6]中的著名背包实例,给出了该背包实例的目前最好结果.此外,对于随机生成的大规模背包实例,通过与文献[3]中的HGA算法对比计算表明:GDS_BPSO算法是求解广义背包问题的一种高效方法.     

对一种新的背包加强算法的破解

自从Shamir提出攻击RalphMerkle和MartinHellman背包密码系统的算法以来,背包密码系统在算法设计上进行了改进,使其在改进后能抵挡Shamir攻击。但由于自身算法设计上可能存在缺陷,其中有一些改进后的背包密码系统会带来新的安全问题。本文是关于一篇题为《一种新的背包加强算法》(注:发表于《电脑与知识》第2004.29期)一文中提出的背包密码算法的破解算法。     

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

Optimal parallel algorithms for the knapsack problem without memory conflicts

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

考虑时间因素的0-1背包调度问题

文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w_i,连续加工时间为t_i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t_i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。     

New multistage knapsack public-key cryptosystem

A new public-key cryptosystem is presented. This system is a multistage trapdoor knapsack cryptosystem. In this system the message is encrypted and decrypted in multistage using a knapsack algorithm. The knapsack algorithm, a security analysis of the multistage system, and a small computer simulation example are presented. The main advantage of the proposed system is that it provides higher security than a single-stage knapsack cryptosystem of the same length.     

一种求解0-1背包问题的快速蚁群算法

0-1背包问题是典型的NP完全问题,且蚁群算法已成功地解决了许多组合优化的难题。因此,文中介绍一种基于蚁群算法求解0-1背包问题的算法,并对此算法进行优化,提出一种求解0-1背包问题的快速蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷,当物品数较大时,也取得了较好的求解质量。仿真实验取得了较好的结果。     

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

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

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

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

The two list algorithm for the knapsack problem on a FPS T20

The advent of parallel machines brought about a controverse in the domain of parallel algorithms: is it worth to conceive parallel algorithms for NP-complete problems? In this work we present a parallel implementation of a sequential algorithm from Horowitz and Sahni for the knapsack problem on a FPS T20. Our aim is to establish some experimental results in order to allow comparisons for forthcoming works. The results show that the development of theory and technology yields the computation tractability of very large knapsack problems.     

基于蚁群系统的多选择背包问题优化算法

提出了一种用蚁群系统求解多选择背包问题的优化算法。该方法利用蚂蚁算法所具有的正反馈特性，再结合变异参数，使算法既有较快的求解速度又有较高的求解精度。实验结果表明，采用此算法能快速有效地解决背包问题。