It is a single-player game. In the beginning, there is a row of integers. In one move the player can take a certain amount of adjacent numbers (let's denote it T). Then the player's points increase with the sum of the chosen numbers. The player can take S moves at most. The goal is to determine the maximum points that can be reached and we have to give the specific moves to reach it.
Example
The numbers: 1 6 8 7 6 2 1 8
S = 2 (max moves)
T = 3 (adjacent numbers to take in one move)
The max points is 32, it can be done like this:
1 6 8 7 6 2 1 8 (we take the bold numbers)
So the two moves are 2 and 6 (they indicate start indexes in the row)
I wrote a recursive code in c# that works if we have few numbers, but takes too long if e.g. has 3000 numbers, 100 max moves and T = 20.
My idea is to first count the points we will get for each number. Then try every possible combination, and store the one that gives me the most points.
So my question is how it can be made it faster?
class Value
{
public int idx = -1;
public int num = -1;
public Value(int idx, int num)
{
this.idx = idx;
this.num = num;
}
}
class Program
{
const int N = 8;
static int S = 2;
static int T = 3;
static int[] numbers = new int[N] { 1, 6, 8, 7, 6, 2, 1, 8 };
static List<Value> values = new List<Value>();
static int maxPoint = -1;
static List<Value> result;
static void Main(string[] args)
{
CountInitValues();
Solve(values, new List<Value>(), 0, T);
}
static void Solve(List<Value> remaining, List<Value> numSoFar, int pointSoFar, int StepsRemain)
{
if (remaining.Count == 0 || StepsRemain == 0)
{
if (pointSoFar > maxPoint)
{
maxPoint = pointSoFar;
result = new List<Value>(numSoFar);
}
}
else
{
List<Value> newNum = new List<Value>(numSoFar);
for (int i = 0; i < remaining.Count; i++)
{
List<Value> newRemaining = new List<Value>();
newNum.Add(remaining[i]);
newRemaining.AddRange(remaining.Take(i - T));
newRemaining.AddRange(remaining.Skip(i + T));
int ujPont = pointSoFar + remaining[i].num;
int ujLepes = StepsRemain - 1;
Solve(newRemaining, newNum, ujPont, ujLepes);
newNum.RemoveAt(newNum.Count - 1);
}
}
}
static void CountInitValues()
{
for (int i = 0; i < N - T + 1; i++)
{
int newValue = 0;
for (int j = 0; j < T; j++)
{
newValue += numbers[i + j];
}
Value ee = new Value(i, newValue);
values.Add(ee);
}
}
}