期刊
APPLIED MATHEMATICS AND COMPUTATION
卷 218, 期 12, 页码 6921-6933出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.amc.2011.12.068
关键词
Discounted knapsack problem; Dynamic programming; Problem partition; Core concept
资金
- FCT (Fundacao para a Ciencia e a Tecnologia, Portugal)
- Germany DAAD
The discounted {0-1} knapsack problem (DKP) is an extension of the classical {0-1} knapsack problem (KP) that consists of selecting a set of item groups where each group includes three items and at most one of the three items can be selected. The DKP is more challenging than the KP because four choices of items in an item group diversify the selection of the items. Consequently, it is not possible to solve the DKP based on a classical definition of a core consisting of a small number of relevant variables. This paper partitions the DKP into several easier sub-problems to achieve problem reductions by imitating the core concept of the KP to derive an alternative core for the DKP. Numerical experiments with DP-based algorithms are conducted to evaluate the effectiveness of the problem partition by solving the partitioned problem and the original problem based on different types of DKP instances. (C) 2011 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据