[1]王秋芬,梁道雷[].一种求解0-1背包问题的算法[J].计算机技术与发展,2013,(01):123-127.
　WANG Qiu-fen,LIANG Dao-lei.An Algorithm of Solving 0-1 Knapsack Problem[J].,2013,(01):123-127.
点击复制

一种求解0-1背包问题的算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2013年01期
页码:
123-127
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
An Algorithm of Solving 0-1 Knapsack Problem
文章编号:
1673-629X（2013）01-0123-05
作者:
王秋芬1; 梁道雷[2; 3]
[1]南阳理工学院 计算机与信息工程学院;[2]华东师范大学 计算机系;[3]浙江理工大学 理学院
Author(s):
WANG Qiu-fen; LIANG Dao-lei
关键词:
数学模型; 最优子结构; 递归关系; 跳跃点; 算法
Keywords:
mathematical model; optimal substructure; recursive relation; jump points; algorithm
文献标志码:
A
摘要:
文中针对各种智能搜索算法可能找不到问题的最优解、出现局部收敛,而动态规划、回溯法、分支限界法时间复杂度又比较高的缺点,分析了0-1背包问题的数学模型,刻划了最优解的结构特征,建立了求最优值的递归关系式.进一步分析递归关系式的函数特征,提出了一种求解0-1背包问题的确定性算法,并用 C++程序设计语言编码实现,该算法的时间复杂度为 O(min{nW,2n}).对三组不同规模的数据进行实验,算法运行的结果表明,该算法实际效率较高且总能得到该问题的最优解
Abstract:
Intelligent search algorithm may not find the optimal solution of the problem and may exit the phenomenon of the local conver-gence. The time complexity of dynamic programming,backtracking,branch and bound method is relatively high. In order to solve these problems,analyze the mathematical model of the 0-1 knapsack problem,and discuss the structure characteristics of the optimal solution. At the same time,it establishes the recurrence relation which is used to solve the optimal value of the 0-1 knapsack problem. According to the recurrence relation,put forward an algorithm to solve the 0-1 knapsack problem and code the algorithm by using C++. Its time complexity is O(min{nW,2n}). Three groups of different size data are inputted in the algorithm. Their output results show that the algo-rithm is high efficiency and can always get the optimal solution of the problem

相似文献/References:

[1]殷晓玲 夏启寿 范训礼.网络考试系统中成卷模式分析研究[J].计算机技术与发展,2009,(02):205.
　YIN Xiao-ling,XIA Qi-shou,FAN Xun-li.Analysis and Study of Volume Pattern in Network Test System[J].,2009,(01):205.
[2]蔡增玉 刘书如 张建伟 张保威.汉字模糊有穷自动机的研究[J].计算机技术与发展,2008,(03):89.
　CAI Zeng-yu,LIU Shu-ru,ZHANG Jian-wei,et al.Research on Chinese Character Input Processing Models Based on Fuzzy Finite Automaton[J].,2008,(01):89.
[3]罗眉 赵宗涛 田涛.一种基于RDB的数据挖掘技术应用研究[J].计算机技术与发展,2007,(01):27.
　LUO Mei,ZHAO Zong-tao,TIAN Tao.Application and Research of Data Mining Technology Based on RDB[J].,2007,(01):27.
[4]黄红.基于GIS的物流配送系统路径优化的算法[J].计算机技术与发展,2006,(08):46.
　HUANG Hong.Algorithm for Optimizing Route in Logistics Delivering System Based on GIS[J].,2006,(01):46.
[5]万华芳 王彪 程尚 曹云峰.倾转旋翼飞行器配平及仿真分析[J].计算机技术与发展,2010,(11):18.
　WAN Hua-fang,WANG Biao,CHENG Shang,et al.Simulation Analysis and Trim of Tilt Rotor Aircraft[J].,2010,(01):18.
[6]梁志罡.电子邮件病毒传播模型的研究[J].计算机技术与发展,2011,(01):158.
　LIANG Zhi-gang.The Study of E-mail Virus Propagation Model[J].,2011,(01):158.
[7]丁海燕,李辰,侬玮[],等.Web日本语虚拟教师4维导学模型的研究与实现[J].计算机技术与发展,2013,(12):190.
　DING Hai-yan[],LI Chen[],NONG Wei[],et al.Research and Implementation of Web Japanese Virtual Teacher 4-Dimensional Study Guide Model[J].,2013,(01):190.
[8]王世豪,杨红雨,李玉贞,等.多机场地面等待策略数学模型的研究[J].计算机技术与发展,2014,24(02):5.
　WANG Shi-hao[],YANG Hong-yu[],LI Yu-zhen[],et al.Study of Ground-holding Strategy Mathematical Model in Multi-airports[J].,2014,24(01):5.
[9]杨兵,左垒.商业银行客户排队系统及其模型研究[J].计算机技术与发展,2014,24(04):250.
　YANG Bing[],ZUO Lei[].Research on Customer Queueing System and Its Model of Commercial Bank[J].,2014,24(01):250.
[10]赵越. 基于支持向量机的软件质量评价[J].计算机技术与发展,2015,25(12):76.
　ZHAO Yue. Evaluation of Software Quality Based on Support Vector Machine[J].,2015,25(01):76.

更新日期/Last Update: 1900-01-01