An efficient pruning algorithm for value independent knapsack problem using a DAG structure.
Journal
Computers & OR
Journal Volume
22
Journal Issue
3
Pages
321-334
Date Issued
1995
Author(s)
Sun, Cha-Hon
Abstract
In this paper, we propose an efficient pruning algorithm to solve the value independent knapsack problem. It stores all the solutions in a directed acyclic graph (DAG) using only O(M · n) space, where n is the problem size and M is the subset summation. Our algorithm is suitable for the case of M ≪ 2n. Also, we find a symmetric property that can improve many heuristic algorithms proposed in the past. © 1995.
Type
journal article