计算机应用研究
計算機應用研究
계산궤응용연구
Application Research of Computers
2015年
11期
3304-3308
,共5页
0-1 背包问题%贪心程度%区域界定%预期效率%最优解%目标函数值
0-1 揹包問題%貪心程度%區域界定%預期效率%最優解%目標函數值
0-1 배포문제%탐심정도%구역계정%예기효솔%최우해%목표함수치
0-1 knapsack problem%greedy degree%boundary of region%expectation efficiency%best profit%objective func-tion value
对现有的求解0-1背包问题的预期效率模型进行了改进，提出了一种基于贪心程度和区域界定的预期效率模型。贪心程度决定着提前装入背包的物体个数，区域界定决定了动态预期效率计算公式所执行的次数。针对该方法求解0-1背包问题，给出相应的定理证明了方法的正确性。仿真实验表明，该算法能够解决0-1背包问题。与已有动态预期效率算法相比，具有明显的高效性；与萤火虫群算法相比，算法亦具有较快的收敛速度。
對現有的求解0-1揹包問題的預期效率模型進行瞭改進，提齣瞭一種基于貪心程度和區域界定的預期效率模型。貪心程度決定著提前裝入揹包的物體箇數，區域界定決定瞭動態預期效率計算公式所執行的次數。針對該方法求解0-1揹包問題，給齣相應的定理證明瞭方法的正確性。倣真實驗錶明，該算法能夠解決0-1揹包問題。與已有動態預期效率算法相比，具有明顯的高效性；與螢火蟲群算法相比，算法亦具有較快的收斂速度。
대현유적구해0-1배포문제적예기효솔모형진행료개진，제출료일충기우탐심정도화구역계정적예기효솔모형。탐심정도결정착제전장입배포적물체개수，구역계정결정료동태예기효솔계산공식소집행적차수。침대해방법구해0-1배포문제，급출상응적정리증명료방법적정학성。방진실험표명，해산법능구해결0-1배포문제。여이유동태예기효솔산법상비，구유명현적고효성；여형화충군산법상비，산법역구유교쾌적수렴속도。
After optimizing expectation efficiency model that has been applied to solve 0-1 knapsack problem,this paper pro-posed a hybrid algorithm based on greedy degree and expectation efficiency of region limitation models.The former determined which and how many objects could be loaded into knapsack in advance,and the latter restricted the number of running dynam-ic expectation efficiency model.Right after this,this paper gave a related theorem,and it proved the correctness of the pro-posed idea.Experimental results demonstrate that the proposed algorithm can solve 0-1 knapsack problem.Except that,in comparison with the existing dynamic expectation efficiency algorithm and glowworm swarm optimization algorithm,it has high-ly efficient and faster convergence speed.
