# Weighted subset sum problem

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.

• What constraints are imposed on the sequence $a_1,\ldots,a_n$? – Dave Clarke Jun 2 '12 at 15:21
• I do not understand your example 1. Should not that be $2 \cdot 100 + 4 \cdot 40$? And example 2 be $2 \cdot 50 + 3 \cdot 20$? – Dmitri Chubarov Jun 2 '12 at 15:42
• Your examples do not appear to match the sum you have defined... – David Jun 2 '12 at 15:44
• That they are integers is sufficient (that is a constraint in itself). – Dave Clarke Jun 2 '12 at 15:57
• Your summation (in revision 3) in condition 2 does not make sense. Why don’t you write exactly as defined in the PDF? – Tsuyoshi Ito Jun 2 '12 at 16:12

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.
• Note that if you want to obtain $A$, you need $\Theta(NM)$ space, too; you have to keep all computed values plus predecessor information for backtracking (or, alternatively, paths of length $\Theta(N)$ in each of the $\Theta(N)$ maintained values). – Raphael Jun 3 '12 at 12:18