背包问题

摘要： 近年来,运输机场处于发展的黄金时期,因此民航安全问题则显得尤为重要。机场的应急资源调度布局工作是民航安全管理的重要组成部分,而在机场应急资源中,机场消防资源是重中之重。为了有效应对机场消防事件,应预先把恰当数量和种类的资源以合适的配比布置在合适的地方。通过确定不同资源类型关于突发事件的重要程度权重,针对小型机场的布局,利用背包原理,建立资源分配的背包决策模型。在特定区域内得到最佳的消防资源布局方案,为机场的消防站配置与资源布局提供决策建议。

摘要： 针对具有差异化服务质量需求的数据采集任务,提出了一种多无人机协同的数据采集策略,通过优化无人机的三维部署和设备关联,以最大程度地节约设备的功率资源。该联合优化问题属于混合整数非线性规划问题,难以求解,因此提出了一种基于交替迭代优化的无人机部署方法。具体而言,将原始问题分解为设备关联子问题和无人机三维部署子问题,进行交替迭代求解。首先,针对设备关联子问题,将其建模为0-1多背包问题,提出了一种基于动态规划的节能设备关联算法。然后,针对三维部署子问题,考虑设备的需求差异化,提出了一种改进的粒子群算法。最后,对上述过程进行交替迭代,直到无人机三维部署和关联的设备不再变化。实验结果表明,在不同的网络通信场景中,提出的算法能够为物联网设备节约更多的功率资源。

摘要： 根据中长期合同签约中的总量限制问题,建立有效的数学模型。引入背包问题的伪多项式时间复杂度算法,给出合理的解决方案,并从近似度、复杂度等方面对方案进行评估。

摘要： 快递车辆配装问题是指车辆在各快递站点进行货物配送时将价值尽可能大的揽收货物带回配送中心。提出一种求解该问题的带限界函数分支限界算法,搜索树中待处理结点用堆结构存储,结点中存储搜索路径,用设定的搜索下界进行搜索树剪枝,实验结果验证了该算法的有效性。

摘要： 民船装载问题是一个多约束背包问题,解决的是资源优化分配的问题,通过合理的方式对需装载的物品进行船只分配,以取得最大价值,也就是舰船装载的最优方案。本文通过对需解决的问题进行分析,将布谷鸟搜索算法搜索范围广但计算精度不高和粒子群算法收敛速度快但容易陷入局部最优的特点结合起来,进行取长补短,改进提出了分阶段随机布谷鸟粒子群智能优化算法,并用此算法来解决舰船装载问题。通过验证此算法相较之前的算法搜索范围广、收敛速度快、能取得较好的解,有效的解决了此问题,并可在实际中进行推广应用。

摘要： 基于发夹结构DNA的循环杂交放大作用和圆环结构的稳定性,设计了一种类闭环双链DNA模型用于解决0-1背包问题.首先,通过碱基互补配对,将引发DNA固定在圆环DNA单链上形成类闭环双链DNA.然后,利用杂交链式反应技术,借助生物素和链霉亲和素的亲和性,将携带有大量拉曼信号分子的纳米金生物条形码结合到类闭环双链DNA上.最后,通过表面增强拉曼散射技术完成对可行解的筛选.

摘要： 研究了带背包约束的基数公平分配问题,即将给定的n个物品放入m个背包,在不超过背包容量的情况下,使得背包中装入的最小物品数尽可能大.通过预处理,可以假定每一个实例的最优值为k且n=km.得到如下的结果:①当所有背包的容量均相同时,通过对3-划分问题的归约证明了该问题不存在近似比大于2/3的近似算法,并基于贪婪法给出一个目标函数至少为k-1的近似算法;②当背包的容量不等时,通过对,维数值匹配问题的归约证明了该问题不存在近似比大于1/2的近似算法,并基于线性规划取整算法给出一个目标函数至少为k-2的近似算法.

摘要： 为了解决多相控阵雷达跟踪多目标时目标分组和时间规划两方面的问题,基于背包问题提出一种多相控阵雷达多目标跟踪的时间资源管理算法,在时间资源受限时联合实现目标分组和时间规划.使用分段的脉冲重复周期和模糊逻辑优先级法,根据目标的先验信息求得用于跟踪目标的时间资源和优先级,构造时间资源管理模型;基于背包问题将时间规划和目标分组联合考虑,使用跟踪目标优先级之和最大化作为算法的目标函数,通过动态规划的思想求解时间资源模型.仿真结果表明:基于背包问题的算法有效地提高了实现价值率;从背包问题的角度解决多相控阵雷达跟踪多目标的问题,可以在有限时间内跟踪更多的目标,同时保证重要目标的跟踪.

摘要： 为了提高联邦学习的通信效率,针对用户计算能力和信道状态异构的场景,提出了一类基于时分多址接入的用户调度策略,在满足给定单轮模型训练所需计算的样本数量约束下,最小化单轮模型更新的系统时延.理论分析了该调度策略的预期收敛速度,探究收敛性能与系统总时延的均衡关系,并进一步分析最优批大小的选择问题.仿真结果显示,所提算法与基准算法相比,模型收敛速率提升30％以上.

摘要： 为利用象群优化算法求解0-1背包问题(0-1KP),在保留原始象群优化算法优秀探索能力和开发能力的基础上,基于传递函数提出一种二进制象群优化算法(BEHO)。在使用贪心修复与优化法处理不可行解的基础上,利用BEHO给出了一种求解0-1KP的新方法。对于20个大规模0-1KP实例,通过与六种不同算法的计算结果比较表明:BEHO不仅求解精度高,而且求解效率快,在求解大规模0-1KP问题方面有更强的竞争力。

摘要： 背包问题经常应用在资源约束条件下的资源分配中,并在组合数学、计算机科学、复杂性理论和密码学中也有应用.本文给出了常见的几种背包问题,将分布估计算法应用于背包问题.分布估计算法提供了一个新的进化模式,它从有前途的候选解建立概率模型来引导搜索过程.分析个体种群数量、选择比例对算法的影响.仿真结果表明:分布估计算法求解背包问题是可靠有效的;此方法具有较好的可扩展性,修改此算法可解决其他背包问题.

摘要： 组合优化问题的目标是从组合问题的可行解中求出最优解，本文将局部搜索以及模拟退火的策略融入动力学演化算法而得到的一种新的求解组合优化问题的动力学演化算法（HDEA 算法）。并以0-1 背包问题为例，给出了求解0-1 背包问题的混合动力学演化算法的算法描述，并且将该算法的性能与贪婪法作了比较，实验的结果表明HDEA 算法在求解精度上优于贪婪法，这表明了该算法具有较优的性能。

摘要： Agent技术特别是移动Agent是目前计算机科学领域中的一个研究热点，使用移动Agent技术可以采用分布式思想解决一些大规模的复杂问题。本文对0-1背包问题进行了适当的描述，在对目前的一些背包问题求解算法进行分析的基础上，结合移动Agent思想，建立了一个以Aglet为开发平台，通过设计满足问题求解目标的移动A-gent，将背包问题进行分布式求解，最终得到最优结果的求解方案。通过实例对该方案进行测试和验证，问题的求解效率得到了一定的提高。最后指出了该方案存在的不足之处。

摘要： 背包问题是一个典型的NP完全问题。本文基于O/I规划的数学模型，提出了解决该问题的二重结构编码的混合遗传算法；在传统遗传编码方式的基础上提出了一种改进，同时针对背包问题的约束条件给出了部分匹配交叉操作的交叉方式，最后通过有效的遗传算法的实现方案，验证了该算法的科学性和有效性。

摘要： 现有的求解背包问题的算法有一个共同的特点:一旦问题的规模确定后,那么算法所需的存储空间也就确定了,算法不能按照机器的实际存储容量进行调节,无法充分利用机器已有的硬件资源。本文所提出的算法可根据处理机的数目以及存储器的容量来调整算法中的参数,达到充分利用已有的硬件资源,求得最快的求解速度的目的.

摘要： 背包问题是著名的NP难问题之一.基于背包问题的特征,本文提出了基于双邻域移动和双禁忌表的禁忌搜索算法:第一种邻域移动的物理意义是增加背包中的物品数量,第二种邻域移动的物理意义是交换背包内外的不同物品.对两个例子的求解均得到了最优解,表明此算法适合于背包问题.

摘要： 为了使用蚁群算法来解决经典的0/1背包问题,本文比较了旅行商问题和0/1背包问题的不同之处.在原有的蚁群优化模型的基础上扩展了它的应用范围,用来解决0/1背包问题,同时相应的一些参数也得到了优化.实验结果显示了蚁群算法的健壮性和作为启发式算法在解决组合优化难题时的潜力.

摘要： 人工鱼群算法(AFSA)是一种最新提出的新型寻优策略,文中尝试将改进的人工鱼群算法应用到0-1背包问题的求解过程,提出了解决该问题的人工鱼群优化模型并定义了其觅食、聚群、追尾等行为操作.本算法的操作特点是从构造人工鱼简单的底层行为做起,通过各人工鱼个体的局部寻优行为,最终使全局最优值在群体中突现出来.文中给出了利用人工鱼群算法和贪心算法解决背包问题的具体步骤,并进行了实际编程,与简单的遗传算法进行了比较.试验结果表明,改进的AFSA具有较快的全局收敛速度,能有效地克服"早熟"收敛,是一种有效解决0-1背包问题的寻优模式.

摘要： 提出了一种改进的多目标优化问题的蚁群算法。算法选择进化算法的定义的时候,种群中一定数量的个体信忠来源作为中心的扩散,多个中心点之间有一定的距离；群体中的其他个体按照离源个体最近的距离的原则归属于其中一个信息素扩散源；按照信忠素扩散算法,每一信息素扩散源中的个体获得源于中心点的信息素；保留每一代群体中的中心点到下一代种群中,确保了收敛性和维护种群的多样性。最后利用多目标背包问题来测试算法的性能,并与MOA和NSGA-II算法进行了分析比较。结果表明,该搜索效率高,向真实Pareto前沿逼近效果好,得到传播的多种解决方案,是一个多目标优化问题的解决和有效的方法。

摘要： 针对南水北调项目群分期投资的效益问题,给出了数学模型,并利用背包问题的贪婪算法得到了项目群的最大效益及其工程开工顺序的安排情况.给项目投资计划处在选择项目投资阶段的人员以一定的参考,便于资金充分、合理地得到利用,最终得到最大的收益。

摘要： 本发明公开了一种有限资源下的有序背包问题分段动态规划求解方法，包括：对于输入的数据，预设物品数量n，每个物品的序号i、重量和价格，背包承重W；设定状态数组F的最大存储；读取可用内存大小，通过状态数组的最大存储和可用内存大小之间的最小值确定状态数组F的元素数量S；对物品按重量从轻到重进行排序，排序后物品的序号记为j，记录序号j与序号i的对应关系；定义状态数组的行数为n，列数；定义第t阶段背包承重，依次判断每个物品是否被选择放入背包，计算第t阶段背包中物品的总价格；如果满足第一预设条件，则重新定义第t+1阶段背包承重，计算第t+1阶段背包中物品的总价格，直至满足第二预设条件，输出结果。

摘要： 本发明公开了一种基于多背包问题分析的RTDS仿真资源分配方法及其系统，方法包括以下步骤：将电网在满足解耦条件的断面处分隔为若干数量的子网络；计算电网建模所需的仿真存储单元资源总量、每个RACK可用存储资源计算结果；并计算出一次电网模型需要的RACK数量；将划分形成的子网络抽象为待装物体，将每个RACK抽象为背包，建立RTDS仿真资源分配的多背包问题数学模型；求解RTDS仿真资源分配的多背包动态规划算法，并进行RTDS仿真资源分配。本发明能够通过定量分析，有效辅助建模设计人员分配RTDS仿真资源，提升RACK资源分配的合理性和仿真运行的稳定性。

摘要： 本发明公开了基于搜救队算法求解0‑1背包问题的方法及系统，通过从物品搜索范围中随机选取物品构建初始样本空间；从样本空间中查找目标函数值最优的样本点作为样本空间的中心点；根据搜索空间与步长确定每个样本点的搜索空间，并基于搜索空间查找备选样本点，将备选样本点的目标函数值与原样本点的目标函数值进行比较，根据比较结果更新样本空间的样本点；对概率控制参数进行缩小操作，迭代次数加1，若达到终止条件，则终止，否则重复上述步骤。本发明模拟搜救队的救援行为，每个队员保持一定的独立性向其周围搜索，同时组员之间不断协同更新中心点的信息，尝试着向中心搜索，能在得到全局最优解的同时提高求解的收敛速率。

摘要： 本发明公开了一种多目标背包问题的混合蛙跳求解方法，（1）问题信息读取，包括每个背包的每个货物的价值与重量信息和每个背包重量限制信息；（2）初始化算法参数；（3）计算种群中所有个体的目标值，确定非支配解集放入外部存储器；（4）进入快速收敛阶段，对种群根据快速非支配排序结果使用“S”型分组方式划分子组，对各个子组进行基于离散跳跃规则和贪婪生成的局部搜索，将各子组混洗，更新外部存储器，判断目标评价次数是否满足快速收敛阶段终止条件，若不满足，则继续迭代，若满足，则进入下一阶段；（5）进入探索扩展阶段；（6）进入极值挖掘阶段。本发明具有搜索速度快，搜索能力强，规划的背包利润高的优点。

摘要： 本发明公开了一种改进智能优化算法在背包问题中的应用方法，本方法通过利用背包剩余空间进行对具有低价值但相对性价比高的物品与具有高价值但相对性价比低的物品进行部分交换，有效交换后不仅能够提升适应度，还使得优化算法构造的初始解更好，从而提高了优化算法的求解速度，本方法解决在背包问题中使用智能优化算法对不可行解的转换为可行解未进行优化或优化程度不足的问题；通过对解的优化使得解的收敛速度有明显提高，本方法能够使得多种背包问题得以用各式的优化算法高效解决；同时对以背包问题为载体的大型工程类问题得以解决；通过对解优化的改进，使得智能优化算法在解决背包问题时收敛速度加快和求解适应度值更优秀。

摘要： 本发明公开了一种有限资源下的有序背包问题分段动态规划求解方法，包括：对于输入的数据，预设物品数量n，每个物品的序号i、重量和价格，背包承重W；设定状态数组F的最大存储；读取可用内存大小，通过状态数组的最大存储和可用内存大小之间的最小值确定状态数组F的元素数量S；对物品按重量从轻到重进行排序，排序后物品的序号记为j，记录序号j与序号i的对应关系；定义状态数组的行数为n，列数；定义第t阶段背包承重，依次判断每个物品是否被选择放入背包，计算第t阶段背包中物品的总价格；如果满足第一预设条件，则重新定义第t+1阶段背包承重，计算第t+1阶段背包中物品的总价格，直至满足第二预设条件，输出结果。

摘要： 本发明涉及背包问题求解技术领域，公开一种基于改进动态规划算法求解有界背包问题的方法，定义物品种类最大数为N，背包的最大容量为C，物品种类为i，0≤i≤N，每种物品的单个价值为vi，重量为wi，每种物品的个数为ki；定义一个(N+1)×(C+1)二维价值表f，背包容量为j，0≤j≤C；计算余数a，根据容量余数a对容量状态j进行分组，将拥有相同容量余数的容量状态j放在一组计算。根据余数对容量状态j进行分组，对传统动态规划递归公式进行了改进，减少了求解BKP过程带来的冗余计算，同时对改进后的算法进行并行化，随着数据量的增大，本发明比现有的算法拥有更好效率，可实现BKP的快速求解。

摘要： 本发明涉及动态规划技术领域，具体涉及一种考虑主观需求的0‑1背包问题的求解方法及电子设备，包括以下步骤：S1利用主观需求概念，建立考虑决策者主观需求的0‑1背包问题模型；S2利用贪心算子，先考虑主观需求再考虑客观约束，对初始种群进行优化与修正；S3利用局部搜索算子，改进扰动位点的选择方式，实现对局部最优解的扰动；S4将上述算子嵌入到遗传算法得到混合贪心遗传算法；S5利用混合贪心遗传算法对主观需求的0‑1背包问题模型进行求解。本发明对局部最优个体进行扰动以期跳出局部最优并得到更优质的解。本发明的模型以及求解算法在较短的时间内保证解的质量，并通过与简单遗传算法和贪心遗传算法的对比，显示出较好的性能。

摘要： 本发明属于分布式能源交易领域，涉及一种基于能源网络约束和多次背包问题的分布式能源交易撮合方法，包括以下步骤：1)通过设计一种能源调度的增广优化模型，约束用户的交易量为申报量和能源网络限制量的较小值，为分布式交易添加安全校核环节；2)基于传统单次背包模型，以市场成交价值最大为目标，设计一种更符合点对点交易的多次背包模型，对多个买方和卖方进行交易撮合。本发明为能源分布式交易与实际物理调度衔接提供思路，为点对点的分布式交易市场提出普惠高效的撮合模型，对分布式能源交易与实际情况衔接具有较强参考意义。

摘要： 本发明公开了一种利用改进天牛须搜索算法求解0‑1背包问题的方法，属于多目标应用领域。背包问题的可以描述为：有N件物品和一个背包，每件物品有对应的价值和体积，问题是求解出将哪些物品放入背包后不会超过背包的容积，与此同时使得背包内物品的价值总和最大。本发明的方法可以有效的解决传统天牛须搜索算法不能应用于离散型问题的技术问题，同时，将本发明的方法应用于0‑1背包问题进行寻优，得到了较好的结果。