寻找最大值的最优算法

Question

我需要设计一个算法来找到我可以在预定义的(步长)下从int[](步长)中获得的最大值。

输入是我们可以"使用"每个步长的次数;由n2 n5 n10给出。N2表示在数组中移动2个位置，n5表示5个位置，n10表示10个位置。我们只能向前走(从左到右)。

int[]包含值1..5，数组的大小是(n2*2 + n5*5 + n10*10)。起始点是int[0]。

示例:我们从int[0]开始。从这里我们可以移动到int[0+2] == 3, int[0+5] == 4或int[0+10] == 1。让我们移动到int[5]，因为它的值最高。从int[5]可以转到int[5+2]， int[5+5]或int[5+10]等。

我们应该以步长为2、5或10的方式移动数组(每个步长只能使用n2-、n5-和n10次)，这样我们就可以在数组中遍历以收集尽可能多的总和。

输出是可能的最大值。

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

这是一个伪代码的答案(我没有运行它，但它应该可以工作)。

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];
}

调用dp(0, 0, 0, 0)答案是在dp[0][0][0][0]。

如果你想往回走，你可以这样做:

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];
}

但是你的路径没有被完全探索，因为如果索引是负的或者大于数组大小我们就会停止- 1，你可以添加绕行功能，我猜。

Answer 2

这是一个解决方案，但我不确定它是多么优化!

我做了一些优化，但我认为还有很多可以做

我把它和问题中写的例子一起发布了

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 3

你需要计算以下动态规划dp[c2][c5][c10][id] -其中c2是你已经走了2次，c5 - 5, c10 - 10和id -哪里是你目前的位置。我将只写c2和c5的例子，它可以很容易地扩展。

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];
      }  
    }   
  }
}

Answer 4

我知道目标语言是java，但我喜欢python和转换不会复杂。您可以定义一个4维数组dp，其中dp[i][a][b][c]是您可以设置的最大值当你已经有了长度为2、长度为5和长度为c的a、b时，从i位置开始10 。我使用记忆来获得更清晰的代码。

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 5

很像家庭作业。不是测试:

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;
        }
    }
}

有一行你可以取消注释来允许向前和向后移动(我确信有人在评论中说这是允许的，但现在我看到你的帖子说只有向前…)