[Solved]: Weighted subset sum problem

Problem Detail: 

Given an integer sequence $\{ a_1, a_2, \ldots, a_N \}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\{i_1, \dots, i_M\} \subseteq [N]$ with $1 \leq i_1 \lt i_1 \lt \dots \lt i_M \leq N$ such that

$\qquad \displaystyle \sum_{j=1}^M j \cdot a_{i_j}$

is maximized.

---

For instance, if the given sequence is $-50; 100; -20; 40; 30$ and $M = 2$, the best weighted sum arises when we choose positions 2 and 4.

So that we get a value $1 \cdot 100 + 2 \cdot 40 = 180$.

On the other hand, if the given sequence is $10; 50; 20$ and $M$ is again 2, the best option is to choose positions 1 and 2 that we get a value $1 \cdot 10 + 2 \cdot 50 = 110$.

---

To me it looks similar to the maximum subarray problem, but I can think of many examples in which the maximum subarray is not the best solution.

Is this problem an instance of a well studied problem? What is the best algorithm to solve it?

This question was inspired by this StackOverflow question.

Asked By : Vitalij Zadneprovskij

Answered By : Dmitri Chubarov

This problem can be solved by means of dynamic programming. One of the best known dynamic programming algorithms is for the knapsack problem. It may be instructive to compare the two problems.

Let $C(n,m)$ denote the solution to the maximal weighted sum problem for the sequence $a_1, a_2, \ldots a_n$ with a subsequence of length $m$ where $1\leq n\leq N$ and $1\leq m\leq M$.

Then $C(n,m+1) = \mathop{max}(C(n-1,m+1), C(n-1,m) + (m+1) \cdot a_n)$.

To compute $C(N,M)$ this algorithm can be implemented in $O(N M)$ time and $O(N)$ space.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2200