.png){kind=icon}
返回
A MINIMAL ALGORITHM FOR THE MULTIPLE-CHOICE KNAPSACK-PROBLEM
.png){kind=icon}
PRE
AI
DOI：10.1016/0377-2217(95)00015-I.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The Multiple-Choice Knapsack Problem is defined as a 0-1 Knapsack Problem with the addition of disjoined multiple-choice constraints. As for other knapsack problems most of the computational effort in the solution of these problems is used for sorting and reduction. But although O(n) algorithms which solve the linear Multiple-Choice Knapsack Problem without sorting have been known for more than a decade, such techniques have not been used in enumerative algorithms. In this paper we present a simple O(n) partitioning algorithm for deriving the optimal linear solution, and show how it may be incorporated in a dynamic programming algorithm such that a minimal number of classes are enumerated, sorted and reduced. Computational experiments indicate that this approach leads to a very efficient algorithm which outperforms any known algorithm for the problem.
Keyword:
KNAPSACK PROBLEM
DYNAMIC PROGRAMMING
REDUCTION
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
7.7W
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容