华南理工大学学报（自然科学版）
華南理工大學學報（自然科學版）
화남리공대학학보（자연과학판）
JOURNAL OF SOUTH CHINA UNIVERSITY OF TECHNOLOGY(NATURAL SCIENCE EDITION)
2009年
4期
42-45
,共4页
背包问题%组合优化%动态规划
揹包問題%組閤優化%動態規劃
배포문제%조합우화%동태규화
背包问题属于组合优化中的经典问题,它有许多重要的变形,其中以多选择背包问题最为复杂.为更快地求解多选择背包问题,文中首先对该问题进行了理论分析,然后基于动态规划提出了一种新的求解算法,并对一个复杂的案例进行了测试.结果表明,这种新算法比遗传算法快9.4倍,比传统的0-1整数规划求解法快78倍.通过对数学模型的改进可大大降低问题的规模.更重要的是,所用方法可避免求解任何线性规划问题.
揹包問題屬于組閤優化中的經典問題,它有許多重要的變形,其中以多選擇揹包問題最為複雜.為更快地求解多選擇揹包問題,文中首先對該問題進行瞭理論分析,然後基于動態規劃提齣瞭一種新的求解算法,併對一箇複雜的案例進行瞭測試.結果錶明,這種新算法比遺傳算法快9.4倍,比傳統的0-1整數規劃求解法快78倍.通過對數學模型的改進可大大降低問題的規模.更重要的是,所用方法可避免求解任何線性規劃問題.
배포문제속우조합우화중적경전문제,타유허다중요적변형,기중이다선택배포문제최위복잡.위경쾌지구해다선택배포문제,문중수선대해문제진행료이론분석,연후기우동태규화제출료일충신적구해산법,병대일개복잡적안례진행료측시.결과표명,저충신산법비유전산법쾌9.4배,비전통적0-1정수규화구해법쾌78배.통과대수학모형적개진가대대강저문제적규모.경중요적시,소용방법가피면구해임하선성규화문제.
