电子设计工程
電子設計工程
전자설계공정
ELECTRONIC DESIGN ENGINEERING
2012年
11期
1-4
,共4页
核%多维多选择背包问题%B＆B算法%分支定界%解空间
覈%多維多選擇揹包問題%B＆B算法%分支定界%解空間
핵%다유다선택배포문제%B＆B산법%분지정계%해공간
core%MMKP%B&B algorithm%branch-and-bound%solution space
多维多选择背包问题（MMKP）是0-1背包问题的延伸，背包核已经被用来设计解决背包问题的高效算法。目的是研究如何获得一种背包核，并以此高效处理多维多选择背包问题。首先给出了一种方法确定MMKP的核．然后阐述了利用核精确解决MMKP问题的B＆B算法，列出了具体的算法步骤。在分析了算法的存储复杂度后，将算法在各种实例上的运行效果与目前解决MMKP问题的常用算法的运行效果进行了比较，发现本文的算法性能优于以往任何算法。
多維多選擇揹包問題（MMKP）是0-1揹包問題的延伸，揹包覈已經被用來設計解決揹包問題的高效算法。目的是研究如何穫得一種揹包覈，併以此高效處理多維多選擇揹包問題。首先給齣瞭一種方法確定MMKP的覈．然後闡述瞭利用覈精確解決MMKP問題的B＆B算法，列齣瞭具體的算法步驟。在分析瞭算法的存儲複雜度後，將算法在各種實例上的運行效果與目前解決MMKP問題的常用算法的運行效果進行瞭比較，髮現本文的算法性能優于以往任何算法。
다유다선택배포문제（MMKP）시0-1배포문제적연신，배포핵이경피용래설계해결배포문제적고효산법。목적시연구여하획득일충배포핵，병이차고효처리다유다선택배포문제。수선급출료일충방법학정MMKP적핵．연후천술료이용핵정학해결MMKP문제적B＆B산법，렬출료구체적산법보취。재분석료산법적존저복잡도후，장산법재각충실례상적운행효과여목전해결MMKP문제적상용산법적운행효과진행료비교，발현본문적산법성능우우이왕임하산법。
The multidimensional multiple-choice knapsack problem （MMKP） is an extension of the 0-1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem. The purpose of the research is how to obtain a core and use it to solve the MMKP effectively. Firstly, the B＆B algorithm that solves MMKP exactly is presented, and simultaneously, concrete steps are list to explain our algorithm. After the analysis of memory complexity, we compared the algorithm presented in the paper against the specific algorithm for MMKP so far, it completely outperform the previous algorithm.
