java - 寻找最大值的最优算法

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，我们将停止，我猜您可以添加环绕功能。