How do I describe this (graph-)problem for a research paper?
Replace any negative value with zero. Then, think of the numbers in the range $1\dots W$ as vertices in a graph, and think of a pair $(x,y)$ as corresponding to an edge from vertex $x$ to vertex $x+y$ (or to $W$ if $x+y&gt;W$), with weight $f(x,y)$. This graph is a DAG, and what you are looking for are the nonzero edges on a longest path from $1$ to $W$ in this DAG. DAG longest path problems can be solved in time linear in the size of the DAG (here, $O(WH)$); see https://en.wikipedia.org/wiki/Longest_path_problem.