# Finding a series of numbers that maximise $\ \sum f_i(x_i)$

Let $$\ f_1, f_2, ... f_m : \{0, ..., m \} \rightarrow \mathbb Z$$

my task is to find an algorithm that find a series of numbers $$\ x_1, x_2, ..., x_m \in \{ 0, ..., m \}$$ that maximise $$\ \sum_{i=1}^m f_i(x_i)$$ and subjects to $$\ \sum_i^m x_i \le m$$

To be honest I can't really wrap my head around this problem. Any suggestions on ways to look at this problem differently?

• What's the context where you encountered this task? Can you credit the source? – D.W. Jan 8 at 21:51
• @D.W. Just home assignment I gotten on data structures and algorithm course I take. Not sure how should I add credit? – bm1125 Jan 8 at 22:54

Following is a trivial Dynamic Programming algorithm for your problem:

Let $$T$$ denote a table of size $$(m+1)$$ x $$(m+1)$$. Here, $$T[i][j]$$ stores the maximum value of $$\sum_{t = 1}^{i}f_{t}(x_{t})$$ such that $$\sum_{t = 1}^{i}x_{t} \leq j$$.

Induction Case: Since there are $$m+1$$ possible choices for $$x_{i}$$, check each one of them. $$T[i][j] = \max_{p \in \{0,\dotsc,m\} \textrm{ and } p \leq j} \Big\{T[i-1][j-p] + f_{i}(p)\Big\}$$

Base Case: For $$i = 0$$ means there is no function. Therefore, the value is $$0$$. $$T[0][j] = 0 \quad \forall j \in \{0,\dotsc,m\}$$

Output: The algorithm will output $$T[m][m]$$ which is simply the maximum value of $$\sum_{t = 1}^{m}f_{t}(x_{t})$$ such that $$\sum_{t =1}^{m} x_{t} \leq m$$

Running Time Analysis: Since the size of the table is $$O(m^{2})$$ and computing each entry takes $$O(m)$$ time. The overall running time is $$O(m^{3})$$.

• In the induction case, $p \in \{0, \dots, m\}$ should be $p \in \{0, \dots, j\}$ since otherwise $T[i-1][j-p]$ might not exist. – Steven Jan 8 at 18:42
• I have added an extra condition that $p \leq j$. It should take care of that right? – Inuyasha Yagami Jan 8 at 18:44
• Yup! $\phantom{}{}$ – Steven Jan 8 at 18:45
• Hi, Thanks for your answer. Though I'm not sure I understand why $\ \sum_{t=1}^I x_t \le j$ ? – bm1125 Jan 8 at 19:27
• @bm1125 Here, the algorithm is considering only the first $i$ functions. And, it finds the maximum value of their sum when the limit is $j$, i.e. $\sum_{t = 1}^{i} x_{t} \leq j$. Maybe you can stare at the solution for some time, and you will understand. – Inuyasha Yagami Jan 8 at 19:51

This problem can be solved using dynamic programming.

For $$i \in \{1, \dots, m\}$$ define $$F_i(x)$$ as the maximum value $$\sum_{j=1}^i f_j(x_j)$$ attainable for a suitable choice of $$x_1, \dots, x_i$$ such that $$x_1 + \dots + x_i \le x$$. That is: $$F_i(x) = \max_{\substack{x_1, \dots, x_i \in \{0, \dots, m\} \\ x_1 + \dots + x_i \le x}} \sum_{j=1}^i f_j(x_j).$$

As a special case let $$F_0(x) = 0$$. You can then write $$F_i(x)$$, with $$i \ge 1$$, as follows: $$F_i(x) = \max_{y \in \{0, \dots, x\}} \big\{ f_i(y) + F_{i-1}(x-y) \big\}.$$

Computing all values $$F_i(0), \dots, F_i(m)$$ in increasing order of $$i$$ using the above identity immediately yields an algorithm with a running time of $$O(m^3)$$ to compute the optimal value of $$\sum_{i=1}^m f_i(x_i) = F_m(m)$$.

Using standard techniques you can then also find an optimal assignment to $$x_1, \dots, x_m$$.

• A High Five - We posted the same solution at the same time :p – Inuyasha Yagami Jan 8 at 18:43