摘要：狼群算法(wolf pack algorithm,WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法(binary wolf pack algorithm,BWPA)。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题——0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。

摘要：针对目前求解0-1背包问题算法的优缺点,开发了一种新的非递归算法。从计算0-1背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时,归纳得到用抽象程序设计语言Apla描述的非递归算法,并形式化证明了其正确性,在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案。

摘要：在介绍微粒群优化算法及其搜索策略的基础上,根据组合约束优化问题的特点,定义了等值变换、异值变换以及变换序列等概念,有针对性地设计了一种适合求解0-1背包问题的特殊微粒群优化算法。实验证明,改进后的微粒群优化算法在求解0-1背包问题上具有可行性和高效性。

摘要：针对0-1背包问题的数学特征,设计了相应离散算法进行求解。算法在基本正弦余弦算法的框架内,首先采用实数编码进行个体初始化,并设计非线性指数递减函数根据迭代深度调节个体更新步长,借用贪婪修复算子对不可行解进行修复及优化。算法性能采用2组大规模的0-1背包问题进行测试,并通过与同类新兴算法的对比表明,本算法高效、简洁,不仅为0-1背包问题提供了高效率的解决方案,还拓展了正弦余弦算法的应用领域。

摘要：针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包问题的置信传播算法。当算法收敛时,计算每个物体节点的置信度,以确定该物体的装包概率,从而高概率地给出0-1背包问题的解。与其他启发式算法进行了比较,结果表明,该算法具有较好的全局搜索能力。

摘要：为扩充对于经典NP-hard问题中的0-1背包问题的求解方法,模拟生态系统中各物种间相互依存、牵制,最终达到动态平衡的自然机制,提出一种新型仿生算法:牵制平衡算法。算法以种群规模描述设计变量,以牵制关系为优化驱动力,以系统达到稳态为优化目标,设计了自成长函数、牵制函数、成长函数用以描述设计变量的变化规律,促进解的寻优进程。将牵制平衡算法对于10个不同规模0-1背包问题的求解结果与近年来文献数据进行对比,结果显示算法在8个不同规模的问题中能获得当前已知最优解,验证了牵制平衡算法的收敛性与求解性能,表明算法对于0-1背包问题的求解具有有效性和竞争力。

摘要：0-1背包问题在信息密码学和数论研究中有着极其重要的应用。首先对背包问题作了简要描述,然后对0-1背包问题的两种经典算法:动态规划算法、贪心算法给出了具体算法设计及实现过程,最后对两种算法在实现的时间、准确性等性能方面进行了分析和对比。

摘要：在传统求解背包问题的理论基础之上,对难解背包问题进行优化,设计了一种基于绝对贪心策略和预期效率的新算法。针对该算法进行了三组仿真实验,结果表明,算法能够较好地解决一类0-1背包问题,优于贪心算法、回溯法、动态规划算法、分支限界算法,该算法的收敛速度是萤火虫群算法的10倍。经过分析数据的离散程度,确定了该算法的适应范围。

摘要：为了有效求解0-1背包问题,提出一种混合二进制差异演化算法。该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题。此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解。不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性。

摘要：用动态规划算法求解0-1背包问题的时空复杂度为O(nC)。这个空间复杂度在求解大规模问题上是不可接受的。从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法。为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题。该新混合算法的时间复杂度为O(nC);它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O(「n/d」+C),其中d为计算机字长。实验结果表明,混合算法的工作效率与理论分析相同。