1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – juleand Apr 27 at 18:36
  • $\begingroup$ 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.. $\endgroup$ – juleand Apr 27 at 19:08
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Apr 27 at 19:11
  • $\begingroup$ So the average xi is <= 1. Interesting. $\endgroup$ – gnasher729 Apr 27 at 20:13
2
$\begingroup$

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][0],DP[k][1], \cdots, DP[k][k]$.

The base cases is $DP[1][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][0] + 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.

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

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.