Shift-and-merge technique for the DP solution of the time-constrained backpacker problem

► We extend the 2-D knapsack problem to a problem on a directed acyclic graph. ► Objective value is a `terrace' function characterized by a set of corner points. ► We introduce a `scanning-wall' method to update the set of corner points efficiently. ► Shift‐and‐merge dynamic programming algorithm is extended to the 2-D case.