Optimal algorithm for finding max value

Question

I need to design an algorithm to find the maximum value I can get from (stepping) along an int[] at predefined (step lengths).

Input is the number of times we can "use" each step length; and is given by n2, n5 and n10. n2 means that we move 2 spots in the array, n5 means 5 spots and n10 means 10 spots. We can only move forward (from left to right).

The int[] contains the values 1..5, the size of the array is (n2*2 + n5*5 + n10*10). The starting point is int[0].

Example: we start at int[0]. From here we can move to int[0+2] == 3, int[0+5] == 4 or int[0+10] == 1. Let's move to int[5] since it has the highest value. From int[5] we can move to int[5+2], int[5+5] or int[5+10] etc.

We should move along the array in step lengths of 2, 5 or 10 (and we can only use each step length n2-, n5- and n10-times) in such a manner that we step in the array to collect as high sum as possible.

The output is the maximum value possible.

public class Main {

private static int n2 = 5;
private static int n5 = 3;
private static int n10 = 2;
private static final int[] pokestops = new int[n2 * 2 + n5 * 5 + n10 * 10];

public static void main(String[] args) {

    Random rand = new Random();
    for (int i = 0; i < pokestops.length; i++) {
        pokestops[i] = Math.abs(rand.nextInt() % 5) + 1;
    }
    System.out.println(Arrays.toString(pokestops));
    //TODO: return the maximum value possible
}
}

Answer 1

Suspiciously like homework. Not tested:

import java.util.Arrays;
import java.util.Random;

public class Main {

    private static Step[] steps = new Step[]{
            new Step(2, 5),
            new Step(5, 3),
            new Step(10, 2)
    };

    private static final int[] pokestops = new int[calcLength(steps)];

    private static int calcLength(Step[] steps) {
        int total = 0;
        for (Step step : steps) {
            total += step.maxCount * step.size;
        }
        return total;
    }

    public static void main(String[] args) {

        Random rand = new Random();
        for (int i = 0; i < pokestops.length; i++) {
            pokestops[i] = Math.abs(rand.nextInt() % 5) + 1;
        }
        System.out.println(Arrays.toString(pokestops));

        int[] initialCounts = new int[steps.length];
        for (int i = 0; i < steps.length; i++) {
            initialCounts[i] = steps[i].maxCount;
        }

        Counts counts = new Counts(initialCounts);
        Tree base = new Tree(0, null, counts);
        System.out.println(Tree.max.currentTotal);

    }


    static class Tree {
        final int pos;
        final Tree parent;
        private final int currentTotal;

        static Tree max = null;

        Tree[] children = new Tree[steps.length*2];
        public Tree(int pos, Tree parent, Counts counts) {
            this.pos = pos;
            this.parent = parent;
            if (pos < 0 || pos >= pokestops.length || counts.exceeded()) {
                currentTotal = -1;
            } else {
                int tmp = parent == null ? 0 : parent.currentTotal;
                this.currentTotal = tmp + pokestops[pos];
                if (max == null || max.currentTotal < currentTotal) max = this;
                for (int i = 0; i < steps.length; i++) {
                    children[i] = new Tree(pos + steps[i].size, this, counts.decrement(i));
                    // uncomment to allow forward-back traversal:
                    //children[2*i] = new Tree(pos - steps[i].size, this, counts.decrement(i));
                }
            }
        }
    }

    static class Counts {
        int[] counts;

        public Counts(int[] counts) {
            int[] tmp = new int[counts.length];
            System.arraycopy(counts, 0, tmp, 0, counts.length);
            this.counts = tmp;
        }

        public Counts decrement(int i) {
            int[] tmp = new int[counts.length];
            System.arraycopy(counts, 0, tmp, 0, counts.length);
            tmp[i] -= 1;
            return new Counts(tmp);
        }

        public boolean exceeded() {
            for (int count : counts) {
                if (count < 0) return true;
            }
            return false;
        }
    }

    static class Step {
        int size;
        int maxCount;

        public Step(int size, int maxCount) {
            this.size = size;
            this.maxCount = maxCount;
        }
    }
}

There's a line you can uncomment to allow forward and back movement (I'm sure someone said in the comments that was allowed, but now I see in your post it says forward only...)

Answer 2

I know the target language is java, but I like pyhton and conversion will not be complicated. You can define a 4-dimensional array dp where dp[i][a][b][c] is the maximum value that you can get starting in position i when you already has a steps of length 2, b of length 5 and c of length 10. I use memoization to get a cleaner code.

import random

values = []
memo = {}

def dp(pos, n2, n5, n10):
    state = (pos, n2, n5, n10)
    if state in memo:
        return memo[state]
    res = values[pos]
    if pos + 2 < len(values) and n2 > 0:
        res = max(res, values[pos] + dp(pos + 2, n2 - 1, n5, n10))
    if pos + 5 < len(values) and n5 > 0:
        res = max(res, values[pos] + dp(pos + 5, n2, n5 - 1, n10))
    if pos + 10 < len(values) and n10 > 0:
        res = max(res, values[pos] + dp(pos + 10, n2, n5, n10 - 1))
    memo[state] = res
    return res

n2, n5, n10 = 5, 3, 2

values = [random.randint(1, 5) for _ in range(n2*2 + n5*5 + n10*10)]

print dp(0, n2, n5, n10)

Answer 3

this is a solution but i am not sure how optimal it is !

i did some optimization on it but i think much more can be done

I posted it with the example written in question

import java.util.Arrays;
import java.util.Random;

public class FindMax {


private static int n2 = 5;
private static int n5 = 3;
private static int n10 = 2;
private static final int[] pokestops = new int[n2 * 2 + n5 * 5 + n10 * 10];


public static int findMaxValue(int n2, int n5, int n10, int pos, int[] pokestops) {
    System.out.print("|");
    if (n2 <= 0 || n5 <= 0 || n10 <= 0) {
        return 0;
    }
    int first;
    int second;
    int third;
    if (pokestops[pos] == 5 || ((first = findMaxValue(n2 - 1, n5, n10, pos + 2, pokestops)) == 5) || ((second = findMaxValue(n2, n5 - 1, n10, pos + 5, pokestops)) == 5) || ((third = findMaxValue(n2, n5, n10 - 1, pos + 10, pokestops)) == 5)) {
        return 5;
    }
    return Math.max(Math.max(Math.max(first, second), third), pokestops[pos]);
}

public static void main(String[] args) {

    Random rand = new Random();
    for (int i = 0; i < pokestops.length; i++) {
        pokestops[i] = Math.abs(rand.nextInt() % 5) + 1;
    }
    System.out.println(Arrays.toString(pokestops));
    //TODO: return the maximum value possible
    int max = findMaxValue(n2, n5, n10, 0, pokestops);
    System.out.println("");
    System.out.println("Max is :" + max);
}

}

Answer 4

This is an answer in pseudocode (I didn't run it, but it should work).

fill dp with -1.

dp(int id, int 2stepcount, int 5stepcount, int 10stepcount) {
  if(id > array_length - 1) return 0;
  if(dp[id][2stepcount][5stepcount][10stepcount] != -1) return dp[id][2stepcount][5stepcount][10stepcount];
  else dp[id][2stepcount][5stepcount][10stepcount] = 0;
  int 2step = 2stepcount < max2stepcount? dp(id + 2, 2stepcount + 1, 5stepcount, 10stepcount) : 0;
  int 5step = 5stepcount < max5stepcount? dp(id + 5, 2stepcount, 5stepcount + 1, 10stepcount) : 0;
  int 10step = 10stepcount < max10stepcount? dp(id + 10, 2stepcount, 5stepcount, 10stepcount + 1) : 0;
  dp[id][2stepcount][5stepcount][10stepcount] += array[id] + max(2step, 5step, 10step);
  return dp[id][2stepcount][5stepcount][10stepcount];
}

Call dp(0,0,0,0) and the answer is in dp[0][0][0][0].

If you wanna go backwards, then you do this:

fill dp with -1.

dp(int id, int 2stepcount, int 5stepcount, int 10stepcount) {
  if(id > array_length - 1 || id < 0) return 0;

  if(dp[id][2stepcount][5stepcount][10stepcount] != -1) return dp[id][2stepcount][5stepcount][10stepcount];
  else dp[id][2stepcount][5stepcount][10stepcount] = 0;

  int 2stepForward = 2stepcount < max2stepcount? dp(id + 2, 2stepcount + 1, 5stepcount, 10stepcount) : 0;
  int 5stepForward = 5stepcount < max5stepcount? dp(id + 5, 2stepcount, 5stepcount + 1, 10stepcount) : 0;
  int 10stepForward = 10stepcount < max10stepcount? dp(id + 10, 2stepcount, 5stepcount, 10stepcount + 1) : 0;

  int 2stepBackward = 2stepcount < max2stepcount? dp(id - 2, 2stepcount + 1, 5stepcount, 10stepcount) : 0;
  int 5stepBackward = 5stepcount < max5stepcount? dp(id - 5, 2stepcount, 5stepcount + 1, 10stepcount) : 0;
  int 10stepBackward = 10stepcount < max10stepcount? dp(id - 10, 2stepcount, 5stepcount, 10stepcount + 1) : 0;

  dp[id][2stepcount][5stepcount][10stepcount] += array[id] + max(2stepForward, 5stepForward, 10stepForward, 2stepBackward, 5backForward, 10backForward);
  return dp[id][2stepcount][5stepcount][10stepcount];
}

But your paths don't get fulled explored, because we stop if the index is negative or greater than the array size - 1, you can add the wrap around functionality, I guess.

Answer 5

You need to calculate following dynamic programming dp[c2][c5][c10][id] - where c2 is number of times you've stepped by 2, c5 - by 5, c10 - by 10 and id - where is your current position. I will write example for c2 and c5 only, it can be easily extended.

int[][][][] dp = new int[n2 + 1][n5 + 1][pokestops.length + 1];
for (int[][][] dp2 : dp) for (int[][] dp3 : dp2) Arrays.fill(dp3, Integer.MAX_VALUE);
dp[0][0][0] = pokestops[0];
for (int c2 = 0; c2 <= n2; c2++) {
  for (int c5 = 0; c5 <= n5; c5++) {
    for (int i = 0; i < pokestops.length; i++) {
      if (c2 < n2 && dp[c2 + 1][c5][i + 2] < dp[c2][c5][i] + pokestops[i + 2]) {
        dp[c2 + 1][c5][i + 2] = dp[c2][c5][i] + pokestops[i + 2];
      }  
      if (c5 < n5 && dp[c2][c5 + 1][i + 5] < dp[c2][c5][i] + pokestops[i + 5]) {
        dp[c2][c5 + 1][i + 5] = dp[c2][c5][i] + pokestops[i + 5];
      }  
    }   
  }
}