首页 | 官方网站   微博 | 高级检索  
     

快速求解多选择背包问题
引用本文:鲍江宏.快速求解多选择背包问题[J].华南理工大学学报(自然科学版),2009,37(4).
作者姓名:鲍江宏
作者单位:华南理工大学数学科学学院
摘    要:本文对多选择背包问题的数学模型进行改进,然后基于动态规划提出了一种新的求解算法。在软件设计中采用了空间换效率的策略。然后对一个复杂的测试案例进行计算,并与遗传算法和传统的0-1整数规划求解法进行比较,发现这种新算法的计算速度得到较大较高。该算法的主要优势是:通过对数学模型的改进大大降低问题的规模、不用求解任何线性规划问题、能同时兼容几种背包问题的求解。

关 键 词:多选择背包问题  动态规划  0-1整数规划  演进算法  
收稿时间:2008-3-18
修稿时间:2008-8-27

A Faster Solution to Multiple-Choice Knapsack Problem
Abstract:First, it was analyzed why Multiple-Choice Knapsack Problem (MCKP) was much more complicated than general Knapsack Problems (KP). Then two prime kinds of algorithms for KP were researched in detail, which included determinate mathematical methods and evolution programs, in order to find out the reason why they were inefficient. The mathematical model of MCKP was improved based on these reasons, then a novel algorithm was developed using dynamic programming. Exchanging memory for speed was taken into account during programming. After a complicated case was tested, it turned out that the new algorithm could faster solve than genetic algorithm and the conventional methods for 01 integer programming. Its main advantage are as follows: reducing many dimensions by improving the mathematical model, avoiding to solve any linear programming, being able to solve other KP except for MCKP.
Keywords:multi-choice knapsack problem  dynamic programming  01 integer programming  evolution program
点击此处可从《华南理工大学学报(自然科学版)》浏览原始摘要信息
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号