Dynamic programming based algorithms for the discounted {0‐1} knapsack problem

Dynamic programming based algorithms for the discounted {0‐1} knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20121903
Volume: 218
Issue: 12
Start Page Number: 6921
End Page Number: 6933
Publication Date: Feb 2012
Journal: Applied Mathematics and Computation
Authors: , ,
Keywords: programming: dynamic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.