Group adjacent sections to create groups with biggest value, value is changing in groups

Question

I have sections 1,2,3...44. We can group only adjacent ones and create groups of maximum size S = 4.
There are two possible variations of this problem:

can not overlap at all (preferred)
can overlap only in outer sections (numbers) /i.e. 1+2+3, 3+4+5+6, 6+7+8 ...

Each section (or group) has it's own value, which is calculated in database query. To simplify, let's assume that it is something like:
SELECT COUNT(*) FROM table WHERE section IN (:sectionNumbers)

Where sectionNumbers parameter is array of sections in group (1,2,3 i.e.)
The value is always greater or equal to value of group with less elements. For example group 1+2+3+4 has value of 100 but the same group without element 4 has value of 70(but it could be 100 as well).
Is there an algorithm which can group those sections (numbers) to maximize sum of group values and in same time try to make those groups as small as possible? If there's not such an algorithm, which is the most similar problem to this one? Maybe I can figure out how to solve this with some similar problem solution.
Not every section has to be in group, but if it is possible, merge them.
Correct result for example could be:
Group: [1], [2+3+4+5], [5+6+7+8], [9+10+11+12], [13+14+15+16], [16+17+18], [19+20+21] ...
Value: (11)   (965)      (146)       (242)         (600)         (611)       (94)

In this example is section 1 alone, because value of group 2+3+4+5 (965) is higher then if we group 1+2+3+4 (i.e. 300)

D.W. · Answer

Your problem can be solved with dynamic programming using a straightforward algorithm.  Let $V[i..i+j]$ denote the value of a single group with numbers $i,i+1,dots,i+j$.  You say you know all of those values.  Let $A[i]$ denote the value of the best way to group all of the numbers $1,2,dots,i$.  Then $A[i]$ satisfies the recursive equation
$$A[i] = max(A[i-4] + V[i-3..i], A[i-3] + V[i-2..i], A[i-2] + V[i-1..i], A[i-1] + V[i..i]).$$
Set $A[-3]=A[-2]=A[-1]=A[0] = 0$.  You can evaluate $A[1]$, $A[2]$, $A[3]$, etc. in that order, using a linear scan.  This takes 44 iterations of the loop, and each iteration of the loop uses a few simple lookups and operations, so the total running time will be extremely fast.  Finally, $A[44]$ holds the solution to your answer, i.e., the value of the best way to group the numbers 1,..,44.  If you want to retrieve the grouping itself, you can do that via standard techniques with prev pointers (each time you take a max, remember which one was the largest; or go back and re-compute it).

Group adjacent sections to create groups with biggest value, value is changing in groups

One Answer

Add your own answers!

Ask a Question