# Dynamic programming - maximize sum of functions subject to constraints

Let $$\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$$.

The problem: Maximize the sum $$\sum_{i=1}^{k}f_i(x_i)$$ subject to the the constraint $$\sum_{i=1}^{k}x_i\le k$$

I think we suppose to come up with a polynomial time solution, but i got stuck on identifying the sub-problems and using them.

One direction that i had was creating a list for each function, where both the arguments and the function values are in decreasing order: in each iteration, find the argmax of the function, delete bigger arguments that yield smaller function values, and proceed with the smaller arguments that remain (($$O(k^3)$$ for all functions).

Then use those lists to iterativly construct the optimal solution under the constraint for 1, 2, .. and finally for all $$k$$ functions, Got stuck about here. Not sure if it's a good direction at all...

Would appreciate any assistance.

• This is a part of an homework assignment in a course. A general hint or direction would suffice, i don't want a full solution. – juleand Apr 27 '19 at 18:36
• I'm not sure what you mean. This is from a first basic algorithms course, i said where i was stuck and didn't ask for a full solution. If i'm violating some policy that i didn't know of, i would be happy to know.. – juleand Apr 27 '19 at 19:08
• Sorry that my comment might be misunderstood. I did not imply anything elsewhere. I am going to delete all my comments. I will write an answer. – John L. Apr 27 '19 at 19:11
• So the average xi is <= 1. Interesting. – gnasher729 Apr 27 '19 at 20:13

Let us read the objective again, "maximize the sum $$\sum_{i=1}^{k}f_i(x_i)$$ where $$\sum_{i=1}^{k}x_i\le k$$."

The subproblems or the table entries are $$DP[a][b]$$ for all $$0\le a\le k$$ and $$0\le b\le k$$, where $$DP[a][b]$$ is the maximum value of $$\sum_{i=1}^{a}f_i(x_i)$$ where $$\sum_{i=1}^{a}x_i=b$$. The wanted maximum sum is the maximum of $$DP[k],DP[k], \cdots, DP[k][k]$$.

The base cases is $$DP[b]=f_1(b)$$ for all $$b$$.

How to reduce the computation of $$DP[a][b]$$ to smaller subproblems? The following equality is the critical observation, which is the reason why we have the first dimension "[a]" in the formulation of the subproblems. The other dimension "[b]" comes from the constraint $$\sum_{i=1}^{a}x_i=b$$.

$$\sum_{i=1}^{a}f_i(x_i) = \sum_{i=1}^{a-1}f_i(x_i) + f_a(x_{a}),$$ i.e., $$DP[a][b]$$ is the maximum of the following numbers, \begin{aligned} &DP[a-1][b] + f_a(0),\\ &DP[a-1][b-1] + f_a(1),\\ &\cdots,\\ &DP[a-1] + f_a(b).\\ \end{aligned}

Exercise 1. Using dynamic programming to maximize the sum $$\sum_{i=1}^{k}f_i(x_i)$$ subject to the the constraint $$\sum_{i=1}^{k}x_i\le n$$, where $$n$$ is a given integer.

Exercise 2. Using dynamic programming to maximize the sum $$\sum_{i=1}^{k}f_i(x_i)$$ subject to the the constraint $$\sum_{i=1}^{k}x_i= n$$, where $$n$$ is a given integer.

Exercise 3. Using dynamic programming to maximize the sum $$\sum_{i=1}^{k}f_i(x_i)$$ subject to the the constraint that for all $$j$$, $$|x_{j+1}-x_{j}|\le n$$, where $$n$$ is a given integer.

• Thank you very much, i now see i didn't pay enough attention for clearly specifying the sub problems. – juleand Apr 27 '19 at 20:19