We know that solving the optimization problem such as $$\max_{y_1, \dots,y_n} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$ $$y_i \in \mathbb{N}_0$$ is easy and can be done via dynamic programming (Viterbi algorithm). See the following figure for the inspiration:
The question is: how to solve the following problem efficiently?
$$\max_{y_1 + \dots + y_n=c} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$ $$y_i \in \mathbb{N}_0 \\ c \in \mathbb{N}_0$$
I have two solutions. The first one is Integer Linear Programming (ILP) which is known to be NPC in general. The second one is a polynomial Dynamic Programming (DP) algorithm.
ILP idea is the following:
$$ \max \sum_{(u, v) \in E} x_{uv} l_{uv} \\ \text{subject to} \\ \sum_{(u, v) \in E} x_{uv} = \sum_{(v, w) \in E} x_{vw} \quad \forall v \in V \setminus \{s,t\} \\ \sum_{(u, t) \in E} = 1 \\ \sum_{(u, v) \in E} x_{uv} c_{uv} = C \\ \text{variables} \\ x_{uv} \in \{0, 1\} \quad \forall (u, v) \in E \\ \text{parameters} \\ C \in \mathbb{N}_0 \\ l_{uv} \in \mathbb{R} \quad \forall (u, v) \in E \\ c_{uv} \in \mathbb{N}_0 \quad \forall (u, v) \in E $$
where $t$ is the sink node, $C$ is the total cost from $_1+\dots+_=C$, $l_{uv}$ is the length between every two nodes $u$ and $v$ (the same as $_{,+1}(_,_{+1})$ in the question). $c_{uv}$ maps to $y_i$.
In other words, this is ILP formulation of longest path with an additional constraint $\sum_{(u, v) \in E} x_{uv} c_{uv} = C$. If someone is interested in an efficient DP solution, write me a private message.