Problem $2.$ Solving equations $(10$ points$)$

Describe an algorithm $($using DP$.$ Format is given below.$)$ that takes as input four positive integers a$,$b$,$c and D$,$ and outputs non$-$negative integers x$,$y$,$z that approximately solves ax$+$by$+$cz~~D$.$ Specifically, you should find x$,$y$,$z such that ax$+$by$+$cz is as close to D as possible $($either lower or higher$).$

Examples:

For $3$x$+5$y$+13$z~~$7,$ a best solution is x$=2,$y$=$z$=0$x$=$y$=1$ and z$=05$x$+11$y$+16$z~~$29,$ the best solution is x$=6,$y$=$z$=05$x$+11$y$+16$z$=305$x$+11$y$+16$z$=27$x$=0$ and y$=$z$=1$ O$($D$)($or better$).$

Hint: Suppose a$<=$b$<=$c$,$ in what the range around D can the optimal value lie?

Format:

$1.$Clearly state what the subproblems are. The best way to do it is by writing what OP T$()$ stands for.

$2.$ Explicitly write the recursive formula used to compute OP T$()$ and write its proof of correct$-$ness.

$3.$ Write the DP algorithm to compute the optimal value. Analyze its running time. $($No additional proof of correctness is needed.$)$

$4.$ Write the backtracking algorithm to identify the set with the optimal value. Analyze its running time.