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$? Jun 2, 2012 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$? Jun 2, 2012 at 15:42
• Your examples do not appear to match the sum you have defined... Jun 2, 2012 at 15:44
• That they are integers is sufficient (that is a constraint in itself). Jun 2, 2012 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? Jun 2, 2012 at 16:12

1 Answer

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.

• 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, 2012 at 12:18