An efficient pruning algorithm for value independent knapsack problem using a DAG structure

In this paper, the authors 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. The present algorithm is suitable for the case of M•2ⁿ. Also, the authors find a symmetric property that can improve many heuristic algorithms proposed in the past.