How can we express an integer linear program as a dynamic program? (Operations Research) We are given the following integer linear program:
\begin{equation}
\begin{array}{c}
\max x_{1}+2 x_{2}+2 x_{3}+3 x_{4} \\
\text { such that } 2 x_{1}+3 x_{2}+x_{3}+2 x_{4} \leq 4, \\
\text { where } x_{1}, x_{2}, x_{3}, x_{4} \in\{0,1\}
\end{array}
\end{equation}
The task is to express this as a dynamic program.
I know that we have to simplify a complicated problem by breaking it down into simpler sub-problems in a recursive manner. However, I cannot figure out how to do so in such a context, no recursive pattern comes to mind.
Help much appreciated.
 A: Let $v_i$ be the objective coefficient of $x_i$, and let $w_i$ be the constraint coefficient of $x_i$.
Let $f(k,b)$ be the maximum when you restrict to the variables $x_1,\dots,x_k$ and a budget of $b$, so that the original problem is to compute $f(4,4)$.  By conditioning on the value of $x_k\in\{0,1\}$ we obtain DP recursion
$$f(k,b) = \max\{f(k-1,b), v_k+f(k-1,b-w_k)\}$$
A: Let $f(x) = x_1 + 2x_2 + 2x_3 + 3x_4$ denote your objective with $x =(x_1, x_2, x_3, x_4) \in \{0,1\}^4$ and $g(x) = 2x_1 + 3x_2 + x_3 + 2x_4 - 4 \leq 0$ the constraint. As $f$ is increasing in all of its arguments, $x_i = 1$ if the constraint allows it. Assume there is a given history $(x_1, x_2, x_3)$ of decisions. Now we determine the optimal $x_4^*$ with respect to any history $(x_1,x_2,x_3) \in \{0,1\}^3$ and $g(x) \leq 0$ [some histories are not feasible (e.g. $(1,1,1)$) and will be basically overwritten by previous decisions (i.e. if $(x_1,x_2) = (1,1)$, then $x_3 = 0$ such that $(1,1,1)$ is a branche that will never be reached)]
\begin{align}
x_4^*(0, 0, 0) = 1\\
x_4^*(1, 0, 0) = 1\\
x_4^*(0, 1, 0) = 0\\
x_4^*(0, 0, 1) = 1\\
x_4^*(1, 1, 0) = 0\\
x_4^*(1, 0, 1) = 0\\
x_4^*(0, 1, 1) = 0\\
x_4^*(1, 1, 1) = 0
\end{align}
Next we determine $x_3^*$ with respect to given $(x_1,x_2)$ and the constraint
\begin{align}
x_3^*(0,0) = 1\\
x_3^*(1,0) = 1\\
x_3^*(0,1) = 1\\
x_3^*(1,1) = 0
\end{align}
Apparently $x_2^*(0) = 1$ and  $x_2^*(1) = 0$.
So we are left with the problem
\begin{align}
\max_{x_1 \in {0,1}} f(x_1, x_2^*(x_1), x_3^*(x_1, x_2^*(x_1)), x_4^*(x_1, x_2^*(x_1), x_3(x_1, x_2^*(x_1))))
\end{align}
If $x_1 = 0$, then $x_2^*(0) = 1$ , $x_3^*(0,1) = 1$, $x_4^*(0,1,1) = 0$ and if $x_1 = 1$, then $x_2^*(1) = 0$ , $x_3^*(1,0) = 1$, $x_4^*(1,0,1) = 0$. So you would need to compare $f(0,1,1,0) = 4$ and $f(1,0,1,0) = 3$. Sucht that $(0,1,1,0) = \arg\max_x\{f(x) \mid g(x) \leq 0\}$ is immediate.
