Given a list of curves and an input value, find the optimal partitioning of the input value

Question

I have a list of curves, all of which have similar formulation but with different coefficients:

• $\large{f_1(x)=\frac{x(A_1C_1+B_1D_1)^2}{A_1x(A_1C_1+B_1D_1)+D_1^2}}$
• $\large{f_2(x)=\frac{x(A_2C_2+B_2D_2)^2}{A_2x(A_2C_2+B_2D_2)+D_2^2}}$
• $\dots$
• $\large{f_n(x)=\frac{x(A_nC_n+B_nD_n)^2}{A_nx(A_nC_n+B_nD_n)+D_n^2}}$

---

Given a positive value of $x$, I want to find a partition of positive values $\{x_1,x_2,\dots,x_n\}$ such that:

• $\large\sum\limits_{i=1}^{n}x_i=x$
• $\large\sum\limits_{i=1}^{n}f_i(x_i)$ is as high as possible

---

What possible approach should I take in order to tackle this challenge?

For all it matters, the coefficients are known to be positive integers.

Answer 1

You can solve the problem via dynamic programming, just like the unbounded knapsack problem. Equivalently, solve a longest path problem in a directed acyclic graph.