.png){kind=icon}
Return
Dynamic programming based algorithms for the discounted {0-1} knapsack problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2011.12.068.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Discounted knapsack problem
Dynamic programming
Problem partition
Core concept
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSave
ShareSaveShareSaveShareSaveShareSave
View more