Shift-and-merge technique for the DP solution of the time-constrained backpacker problem
We formulate the time-constrained backpacker problem as an extension of the classical knapsack problem (KP), where a backpacker travels from a origin to a destination on a directed acyclic graph, and collects items en route within the capacity of his knapsack and within a fixed time limit. We present a dynamic programming (DP) algorithm to solve this problem to optimality, and a shift-and-merge DP algorithm to solve larger instances. The latter is an extension of the list-type DP, which has been successful for one-dimensional KPs, to the two-dimensional case. Computational experiments on a series of instances demonstrate advantage of the shift-and-merge technique over commercial MIP solvers.
dynamic programming two-dimensional 01 knapsack problem combinatorial optimization