Finding the most probable labeling that sums up to some integer 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$$
 A: 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.
