A "packing" optimisation problem with application in dynamic programming

Question

I'm interested in the following problem :

Input : an integer $n$, and $k$ increasing functions $f_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f_i(0)=0$ for all $1\le i \le k$

Output : $k$ integers $n_1,\dots,n_k$, such that $n_1+\dots+n_k=n$, with $0\le n_i\le n$

Goal : Maximize $\sum_{i}f_i(n_i)$

My question is : If we suppose that $k=n$, or simply $k=\Omega(n^\delta)$ for some $\delta>0$, is it possible to find the optimal solution in polynomial time (in $n$) ?

What if we first consider very simple functions like : $\forall i,m, f_i(m+1)-f_i(m)\in\{0,1\}$ ?

Such a result could possibly have interesting applications for dynamic programming

Answer 1

Yes. This can be solved in polynomial time using a straightforward dynamic programming algorithm. You build a table $A[\cdot,\cdot]$ where $A[i,m]$ denotes the maximal value of $f_1(n_1)+\dots+f_1(n_i)$ subject to the requirement that $n_1,\dots,n_i$ be a partition of $m$, i.e., $n_1 + \dots + n_i = m$. The entries satisfy the following recursive relation:

$$A[i,m] = \max \{A[i-1,m-t] + f_i(t) : 0 \le t \le m\}.$$

You can fill in this array using the recursive relation in $O(kn^2)$ time, which is polynomial in $n$. Then, $A[k,n]$ contains the answer to your problem.