如何通过动态规划方法解决这个问题？

Question

我正在解决一个关于数组的基本问题。问题陈述如下：

SIS开了一个篮球场，所以Demid决定举行篮球练习课。有2⋅n名学生来参加Demid的练习课，他将这些学生排成两行相同大小的队伍（每一行恰好有n个人）。学生在每一行中按照从左到右的顺序编号为1到n。

现在，Demid想选择一个队伍打篮球。他将从左到右选择球员，并且除了第一个选中的球员之外，每个选中球员的索引都严格大于上一个选中球员的索引。为了避免偏袒其中一个队伍，Demid会这样选择学生，使得没有连续的已选学生属于同一行。第一个学生可以从所有2n个学生中选择（没有其他限制），并且团队可以由任意数量的学生组成。

为了组成一支完美的队伍，Demid认为他应该选择这样的学生，即所有被选择学生的身高总和最大。帮助Demid找到可以选择的团队中身高总和最大的球员。

例如，如果输入是：（第一行包含n的值，接下来跟随两行，包含学生的身高）

5
9 3 5 7 3
5 8 1 4 5

我的处理方式是：

#These are global variables and functions. 

int arr1[n],arr2[n],sum=0,max=0;
void func1(i)
{
   if(i==n)
   {
      if(sum>max)
         max=sum;
      return;
   }
   sum+=arr1[i];
   for(k=i+1;k<n;k++)
      func2(k);
}

void func2(i)
{
   if(i==n)
   {
      if(sum>max)
         max=sum;
      return;
   }
   sum+=arr2[i];
   for(k=i+1;k<n;k++)
      func1(k);
}

#Caller module. In main
for(i=0;i<n;i++)
{
   sum=0;
   func1(i);
}

这是我的算法，基于我的逻辑推理。我还没有编写代码，稍后会编写。因此请随意指出代码中的任何逻辑错误。 我知道这可以使用动态规划方法轻松解决，而这个算法并不是那样的。在这种情况下，函数将是什么样子？ 就我所知，这个算法中的问题是我需要全局声明arr1和arr2，而我在主函数中获得n的值。

- Hamsa

---

请查看哪个网站？以获取一般问题。 - Prune

欢迎来到StackOverflow。请遵循帮助文档中建议的发布准则，这些建议在您创建此帐户时已经提供了。主题、如何提问和... 完美问题适用于此处。StackOverflow不是设计、编码、审查或教程资源。如果您清楚地描述您的算法，我们可以对此进行评论；如果您展示了代码的功能问题，我们可以提供帮助。 - Prune

要求我们为您编写DP解决方案超出了Stack Overflow的范围。 - Prune

int arr1[n],arr2[n] -- 如果 n 是一个变量，这不是有效的 C++。 - PaulMcKenzie

你的算法完全跳过了第二行中的第一个玩家（arr2 [0]）。此外，“sum”不应该是全局变量，你需要将其作为参数传递给“func1”和“func2”。 - Konstantin Murugov

Answer 1

这里可以采用动态规划的方法。有两个选择：从A中选择或跳过，从B中选择或跳过。我们的自底向上递推公式如下：

// Choose from A or skip
m[i][0] = max(A[i] + m[i - 1][1], m[i - 1][0])
// Choose from B or skip
m[i][1] = max(B[i] + m[i - 1][0], m[i - 1][1])

JavaScript代码：

function f(A, B){
  let m = new Array(A.length + 1)

  for (let i=0; i<=A.length; i++)
    // [a or skip, b or skip]
    m[i] = [0, 0]

  for (let i=1; i<=A.length; i++){
    // Choose from A or skip
    m[i][0] = Math.max(
      A[i-1] + m[i - 1][1], m[i - 1][0])
    // Choose from B or skip
    m[i][1] = Math.max(
      B[i-1] + m[i - 1][0], m[i - 1][1])
  }

  return Math.max(...m[A.length])
}

var a = [9, 3, 5, 7, 3]
var b = [5, 8, 1, 4, 5]

console.log(f(a, b))

- גלעד ברקן

---

你的回答没有描述它如何遵守“不允许相邻的选定学生属于同一行”的规则。 - Ben Voigt

但是子序列A#1，skip，A#3也不被允许。 （如果实用程序严格为非负数，例如球员身高，则该序列始终会被合法的A#1，B#2，A#3所支配....但这种结构依赖性的“弹射以符合规则”需要文档记录） - Ben Voigt

就像我之前说的那样，如果效用值（这里指玩家身高）严格为正数，它不会提供最终错误的解决方案。但事实是，您正在创建不可行的中间解，并依靠支配来选择可行解...对我来说，这很重要，否则如果将来更改问题定义（引入负效用），可能会选择一个不可行的解作为最优解。或者，您可以像@Gene一样避免首先创建不可行的解决方案。 - Ben Voigt

@גלעדברקן 我认为你的代码总是从数组B中取i+1个元素，如果从数组A中选择了第i个元素，反之亦然。但是根据我所学习的问题，如果从数组A中选择了第i个元素，那么我将有灵活性从数组B中选择i+1到n中的任何一个元素。正是由于这个限制，我无法编写递归步骤。希望你能理解。 - Hamsa

@גלעדברקן 是的，你说得对。我尝试了每种可能的组合，每次都成功了。做得很好。我有点理解这个逻辑，但如果你能提到底层逻辑/理论/数学，那将对未来遇到此问题的访问者和我自己非常有帮助。再次感谢你的出色方法。 - Hamsa

Answer 2

我们可以定义两个函数A和B。A(i)是我们通过从第一行选择索引i或更大的下一个玩家可以获得的最大高度。B(i)是第二行相同的情况。现在我们可以用B来表示A，用A来表示B。例如，A(i)是对所有索引k（i或更大）进行最大值运算，通过从第一个集合中选择第k个元素再加上从第二个集合中选择k+1或更高的元素所能获得的最大值。B(i)是对称的。

A(i) = max_{k=i..n} a[k] + B(k + 1); A(n) = a[n]
B(i) = max_{k=i..n} b[k] + A(k + 1); B(n) = b[n]    

答案将是max(A(1), B(1))。

一种简单的方法是按照所写的代码使用两个记忆化函数进行编码。我将使用C而不是C++，并进行调整以使用基于0的索引。

#include <stdio.h>

#define N 5
int a[] = {9, 3, 5, 7, 3};
int b[] = {5, 8, 1, 4, 5};
int Avals[N], Bvals[N];

int B(int i);

int A(int i) {
  if (i >= N) return 0;
  if (Avals[i]) return Avals[i];
  int max = 0;
  for (int k = i; k < N; ++k) {
    int val = a[k] + B(k + 1);
    if (val > max) max = val;
  }
  return Avals[i] = max;
}

int B(int i) {
  if (i >= N) return 0;
  if (Bvals[i]) return Bvals[i]; 
  int max = 0;
  for (int k = i; k < N; ++k) {
    int val = b[k] + A(k + 1);
    if (val > max) max = val;
  }
  return Bvals[i] = max;
}

int main(void) {
  int aMax = A(0);
  int bMax = B(0);
  printf("%d\n", aMax > bMax ? aMax : bMax);
  return 0;
}

我认为有一种方法可以用简单的循环替换记忆化递归，按严格递减的索引顺序访问Avals和Bvals的元素，但具体细节需要您自己解决。这将产生更小、更快的代码。

- Gene

---

我欣赏你的方法。它与我的方法相似。我认为这个问题缺乏具体的DP方法，因为DP问题需要递归步骤，而递归是“一个函数调用自身”。同时，由于问题提出者只建议采用DP方法，所以我会按照这种方法进行。哈哈 - Hamsa

@Excelsior 当然这个解决方案是DP。A调用B，B调用A。这被称为相互递归。 - Gene

哦，好的！我从未使用过它，所以我不知道。谢谢你分享你的答案。 - Hamsa