对背包问题的计算机算法研究

<正>1问题定义背包问题定义:设有不同价值不同重量的物品n件。求从这n件物品中选取部分的方案,使得重量之和不超过指定的限制,但是价值之和最大。上述问题的形式化描述如下:极大化∑PiXi约束条件∑WiXi≤M其中Xi=0或1,Pi≥0,Wi>0,1≤j≤n背包问题是已经证明了的NP完全问题,这意味着我们有可能在多项式时间内求得其最优解。回溯法是解决NP完全问题的常用方法之一。2问题解法2.1算法思想设number件物品的重量放在数组a[i].weight,物品的价值放在数组a[i].value.采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于option[i],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[i]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值设为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv时,该方案不会再被考察。这同时保证函数后找到的方案一定比前面的方案更好。     

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

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

计算K（≥2）序线性递归N方程组的一种有效并行方法

本文提出计算K(≥2)序线性递归N方程组的一种有效并行方法,当k<相似文献   

一种用于求解0-1背包问题的动态伸缩算法

针对0-1背包这个非确定多项式（NP）完全难题,提出一种新的启发式搜索算法来解决0-1背包问题。算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,通过用启发式策略选择交换背包内和背包外物品的位置,采用动态伸缩策略调整背包大小,选取种群中部分优秀解进入下一代继续进行优化。通过5个背包实例进行测试,实验结果表明该算法收敛速度快、求解精度高,并且具有良好的稳定性。     

可重复性背包问题的探讨

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

收缩背包问题的DNA算法

收缩背包问题是标准背包问题的一个扩展,其中背包的容量为所装物品数量的非增函数。本文提出了基于分子生物技术的求解收缩背包问题的DNA算法,首先将其约束条件进行分解;然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板,在链接酶的作用下将它们进行链接反应,生成代表任意物品组合的DNA链;再通过基本的生物操
作筛选出可行解;最后比较各个可行解对应的目标函数值,进而得到最优解。     

笔记本电脑推荐

华硕F9J处理器IntelCore2D uo T7400内存2×1G B D D R2667M H z硬盘日立160G SA TA光驱D V D刻录机显示屏12.1英寸W X G A TFT LCD,最佳分辨率1280×800显卡N V ID IA G eforceG o7300128M,最大可扩充至512M芯片组Intel945PM无线网卡802.11a/b/g重量1.92K g(含3芯电池)系统W indow sV istaU ltim ate简体中文版保修2年全球联保价格16888元索尼VGN-C22CH/B处理器IntelCore2D uo T5500(1660M H z)内存768M B硬盘80G B显示屏13.3英寸显卡N V ID IA G eforceG O7400(64M B)光驱D V D-M ulti重量2.3K g系统M i…     

一类难解0/1背包问题的有效搜索算法

针对一类难解0/1背包问题,给出背包最大价值与物品集中元素的组合特性,在价值密度比贪心策略的基础上,采用组合交叉搜索策略设计一个快速搜索算法——ZHKnap。实验表明,在多项式时间复杂度内得到的解的质量优于目前算法的结果,证明最优解与元素的重量和价值参数的大小分布无关,而只与元素的重量及背包零头的组合相关。     

并行找近似最大值的位对分技术

<正> 设K是一个数据集,其中每个元素a∈K的键是整数,都可用P位二进制a_1a_2…a_p表示。K 上的全序关系R 定义为:若a_i=b_i(1≤i≤l),a_(l+1)>b_(l+1),o≤lb。显然B=(K,R)是一个数据结构。我们考察在B 上解最大元问题。对并行找最大元,[1]已有相当好的结果。Valiant 利用图论结果得出:若处理机台数为n,每台处理机都以二元比较作为基本运算,则对n 元找最大元的并行比较次数为t_(max)(n)≥log_2log_2n-const事实上若考虑计算机的系统开销,则不论有多少台处理机可用,因问题有n 个输入,分析树高至少为log_2n。     

DEDS的集结与输入-输出等价

作者对有限缓冲器容量的柔性制造系统(FMS)建模,并对所建的高维模型完成了集结和保持输入-输出等价的算法.该模型和集结、输入-输出等价算法已成功地用于FMS的摄动分析. 设有M台机床,m种工件.设工件访问机床的次序不逆向,但并不要求工件必须顺序经过M台机床. 记u_i(1≤i≤M)为i机床投入运行时刻;(M+1≤i≤M+m)为(i—M)工件投料时刻;x_(ij)为j机床加工i工件的开始时刻;y_i(1≤i≤m)为i工件加工完毕时刻;(m+1≤i≤m+M)为(i—m)机床加工完毕时刻;a_(ij)为j机床加工i     

1998年第14期擂台赛点评

问题:已知n个点(n≤200),任意两个相邻点i,i+1之间都有m条边(2≤m≤10),每条边有一个权值f_(ij)(1≤i≤n-1,1≤j≤m) ,我们定义从第1点到第n点的所有路径中,长度除以b(2≤b≤50)的余数最小的路径是最优路径。试编一程序求最优路径。     

人工神经网络BP算法通用程序

前言 尽管人工神经网络BP算法仍然存在着某些问题,但它还是一个非常有效的算法,得到了广泛的应用。本文介绍一个通用的BP算法程序。 1.BP算法 对于全连接的BP网络,假设网络共有N层,其中,输入节点为n个,输出节点为m个,网络有N—2个隐层,第i层的神经元数为N_i,则有N_1=n,NN=m;规定第i层第q个神经元的输出为y(i,q),阈值为θ(i,q),其中第1层的输出为输入的样本;从第i层的第s个神经元到第i+1层第q个神经元的连接权为W(i,s,q)。各层神经元的输出满足:     

一次到位分类法

传统的分类法(如交换、插入、选择等),大都从比较两数的大小出发进行分类,而不考虑两数之差的大小,因此分类速度最快为0(nlog_2n),本文介绍一个分类算法,不但利用两数的大小这一信息,同时还考虑两数之差的大小,或者说被排数据的分布规律,从而加快了分类速度。算法具体描述如下:设有未分类数据y(i)1≤i≤N,定义数组     

优化问题的线性逼近与罚函数搜索算法及其收敛性

在本文中,恒假定(H_1):f(x),g_i(x),1≤i≤m,h_j(x),1≤j≤l为一阶连续可微函数. 上述(NP)问题,若用可行方向法等方法求解时,初始点必须是可行点,且在每一步迭代中,为了得到目标函数值下降而又可行的点,除进行一维搜索外往往需要增加辅     

递推公式求值的一个技巧

[问题1]实数数列Ai满足Ai=2×Ai-1-Ai-2+1已知A1 与A2,求An。这是一道非常典型的数学问题,显然,根据提供的公式,我们可以顺次求出A3、A4、A5……An,核心程序如下:Readln(A[1],A[2]);For i:=3 to N doA[i]:=2*A[i-1]-A[i-2]+1;Writeln(A[N]);粗略估算本方法要每次递推求得一项,要进行3次实数运算,那么总共要进行3N次实数运算。这只是一般的常规性思路,直接根据公式进行推导计算来求出答案,我们称为“直接推导法”。那么该问题是不是只能这样解决呢?有没有别的更好的办法呢?下面     

基于动态规划法求解动态o-1背包问题

随机时变背包问题(RTVKP)是一种动态组合优化问题,也是一种典型的NP-hard问题。由于RTVKP问题中物品的价值、重量和背包载重均是动态变化的,导致问题的求解非常困难。在动态规划法基础上,提出了一种求解背包载重随机变化的RTVKP问题的确定性算法,分析了其复杂度和成功求解需要满足的条件。对两个大规模实例的计算表明,该算法是求解RTVKP问题的一种高效算法。     

能行计算复杂性Blum测度的产生性

设P:(?)_0,(?)_1,…,(?)_i,…是一元部份递归函数的一个可接受枚举。称算子F:P→P是一个能行全算子,假若有递归函数S使 (1)((?)i)((?)n):F[(?)i](n)=(?)s(i)(n),且 (2)((?)i):(?)i是递归函数(?)(?)s(i)是递归函数;这时若有(?)r=S,则把r称为能行全算子F的一个指标。 称能行全算子F是能行计算复杂性的Blum测度算子(简称B-算子),假若F满足下述两条Blum公理: (1) ((?)n)((?)i):F[(?)i](n)↓(?)(?)i(n)↓, (2) {〈i,n,m〉|F[(?)i](n)=m}是递归集。 称一个B-算子F的值域{F[(?)i]|i=1,1,…}为一个Blum可接受机器类,F的指标被叫做这个机器类的指标。 设N为非负整数集,M(?)N,称M是Blum可接受机器类的指标集,假若 ((?)r):(r∈M)(?)((?)r是递归函数且((?)B-算子F) ((?)i)(F[(?)i]=(?)(?)r(i)))。 本文的结果是: 定理。Blum可接受机器奥的指标集M是产生集。     

求解多维背包问题的贪心粒子群算法

将多维背包问题的贪心变换和两种求解算法,用于求解具有重量和体积两个约束的背包问题,分别将物品按价值/重量、价值/体积比的凸组合和无穷范数的定义获得两组混合"性价比"权值向量,再以该混合"性价比"权值为依据构造两种贪心粒子群算法(wPSO,infPSO)。数值试验表明,算法wPSO、infPSO不仅大大优于现有粒子群算法,而且表现出优秀、稳定的搜索能力和快速定位最优解的搜索能力。     

机组最优负荷分配中等微增率法的分析及其算法的改进

一、问题的提出给定n台机组,各机组燃料费特性曲线已知为 f_i(p_i)=a_ip_i~2 b_ip_i c_i (i=1,2,…,n)其中a_i,b_i,c_i均为正的常数。各机组上、下限出力为Pimin,Pimax。(i=1,2,…,n)。给定负载荷P_R在n台机组间进行经济负荷分配,可表述为如下数学规划问题: 目标函数:F(p_R)=sum from i=1 to n(a_ip_i~2 b_ip_i c_i)→min (1—1) 满足约束条件:sum from i=1 to m P_i=P_r (1—2) P_(imin)≤P_i≤P_(imax) (1—3) 以上规划问题简称规划A,目前常用的求解该规划的等微增率法,简称算法Ⅰ。其计算框图见文献[2]。     

求解背包问题的更贪心粒子群算法

将粒子群算法与贪心思想相融合,提出一种用于求解0/1背包问题的更贪心混合粒子群算法。对超过背包重量约束的粒子的处理措施是去掉已经装进去且性价比最差的物品,直至满足重量约束为止,这种思想在改善粒子质量的同时避免了通常罚函数方法中敏感的参数选择问题;对当前可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止。通过与文献中基于经典算例的计算结果比较表明,更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都超过了文献中提到的混合遗传算法（HGA）、贪心遗传算法（GGA）和混合粒子群算法（GBPSOA）。