0
$\begingroup$

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?

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

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})$.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Steven Jan 8 at 18:42
  • $\begingroup$ I have added an extra condition that $p \leq j$. It should take care of that right? $\endgroup$ – Inuyasha Yagami Jan 8 at 18:44
  • 1
    $\begingroup$ Yup! $\phantom{}{}$ $\endgroup$ – Steven Jan 8 at 18:45
  • $\begingroup$ Hi, Thanks for your answer. Though I'm not sure I understand why $\ \sum_{t=1}^I x_t \le j $ ? $\endgroup$ – bm1125 Jan 8 at 19:27
  • $\begingroup$ @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. $\endgroup$ – Inuyasha Yagami Jan 8 at 19:51
1
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.