Skip to main content
added 555 characters in body
Source Link
RobPratt
  • 34.3k
  • 2
  • 47
  • 90

Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$. To Let $a_i$ be the constraint coefficient of $x_i$, and let $z_i(x_i)$ be the contribution to the objective value for variable $x_i$. For example, $z_2(x_2) = 5x_2^2-x_2^4$. The boundary condition is $f(0,b)=0$. To derive the Bellman equation as a recurrence for $f(n,b)$ in terms of $f(n-1,.)$, condition on the finite number of choices for the value of $x_n$.: $$f(n,b) = \max_{x_n \in \{0,\dots,\lfloor b/a_n \rfloor\}} (z_n(x_n) + f(n-1,b-a_n x_n))$$ The resulting values of $f$ are as follows: \begin{matrix} n\backslash b &0 &1 &2 &3 &4 &5 &6 &7 \\ \hline 0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 1 &0 &16 &26 &30 &30 &30 &30 &30 \\ 2 &0 &16 &26 &30 &30 &30 &34 &34 \\ 3 &0 &16 &26 &30 &30 &30 &34 &\color{red}{34} \\ \end{matrix}

Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$. To derive a recurrence for $f(n,b)$ in terms of $f(n-1,.)$, condition on the finite number of choices for the value of $x_n$.

Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$. Let $a_i$ be the constraint coefficient of $x_i$, and let $z_i(x_i)$ be the contribution to the objective value for variable $x_i$. For example, $z_2(x_2) = 5x_2^2-x_2^4$. The boundary condition is $f(0,b)=0$. To derive the Bellman equation as a recurrence for $f(n,b)$ in terms of $f(n-1,.)$, condition on the finite number of choices for the value of $x_n$: $$f(n,b) = \max_{x_n \in \{0,\dots,\lfloor b/a_n \rfloor\}} (z_n(x_n) + f(n-1,b-a_n x_n))$$ The resulting values of $f$ are as follows: \begin{matrix} n\backslash b &0 &1 &2 &3 &4 &5 &6 &7 \\ \hline 0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 1 &0 &16 &26 &30 &30 &30 &30 &30 \\ 2 &0 &16 &26 &30 &30 &30 &34 &34 \\ 3 &0 &16 &26 &30 &30 &30 &34 &\color{red}{34} \\ \end{matrix}

Source Link
RobPratt
  • 34.3k
  • 2
  • 47
  • 90

Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$. To derive a recurrence for $f(n,b)$ in terms of $f(n-1,.)$, condition on the finite number of choices for the value of $x_n$.