选择的回溯值

Question

我有一个 c++ 程序，它可以计算一个数组的最大值，前提是不能取数组的两个连续元素。例如： 7 3 4 6 将导致答案 13 。这里我们选择 7 和 6 作为最佳最大值。这是我的递归程序。

#include <iostream>
using namespace std;
int n;

int findMax(int x,int ar[])
{
    if(x < n)
        return max( ar[x]+findMax(x+2,ar), findMax(x+1,ar));
    return 0;

}

int main(){
    int ar[]={1,7,4,4,9,5,12};
    n = sizeof(ar)/sizeof(ar[0]);
    cout<<findMax(0,ar);
    return 0;
}

但是 我对我的程序为此目的选择的数组索引更感兴趣。我怎样才能有效地做到这一点。 在上面的程序中，答案应该是 1,4,6 因为我们选择了数组的第 1、4 和 6 个元素作为最大值。

注意：我正在使用基于 0 的索引。

谢谢。

Answer 1

这绝对不是最有效的解决方案，但可能是实施工作量最少的解决方案：

#include <iostream>
#include <vector>

using namespace std;

int n;

pair<int, vector<int> > findMax(int x, int ar[])
{
  if (x < n) {
    pair<int, vector<int> > max1 = findMax(x + 2, ar);
    const pair<int, vector<int> > max2 = findMax(x + 1, ar);
    max1.first += ar[x];
    max1.second.insert(max1.second.begin(), x);
    return max1.first >= max2.first ? max1 : max2;
  }
  return make_pair(0, vector<int>());
}

ostream& operator<<(ostream &out, const vector<int> &vec)
{
  const char *sep = "";
  for (int value : vec) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  int ar[]={1,7,4,4,9,5,12};
  n = sizeof ar / sizeof *ar;
  const pair<int, vector<int> > maxAr = findMax(0, ar);
  cout << maxAr.first << '\n'
    << maxAr.second << '\n';
  return 0;
}

输出：

28
1, 4, 6

Life demo on coliru

因此，return 值用 std::vector<int> 扩展，它保存当前总和旁边使用的索引。

std::max() 如果我能为 std::pair<int, std::vector<int> > 提供合适的（超载）operator<()，则可以使用

std::max()。为了不让事情变得过于复杂，我只是用 resp 替换了 std::max()。条件。

Answer 2

我认为下面的代码可以满足您的需求。

#include<bits/stdc++.h>
using namespace std;
int n;
void findMax(int arr[], int in, pair< int, vector<int> > tempStore, 
pair< int, vector<int> > &resStore) {
    if(in >=n) {
       if(resStore.first < tempStore.first) {
            resStore.first = tempStore.first;
            resStore.second = tempStore.second;
       }
       return;
    }
    findMax(arr, in+1, tempStore, resStore);
    tempStore.first += arr[in];
    tempStore.second.push_back(in);
    findMax(arr, in+2, tempStore, resStore);
}
int main() {
    int ar[]={1,7,4,4,9,5,12};
    n = sizeof(ar)/sizeof(ar[0]);
    pair< int, vector<int> > resStore, tempStore;
    findMax(ar, 0,tempStore,resStore);
    cout<<"Result Value: "<<resStore.first;
    cout<<"\nResult Index:\n";
    for(int i=0; i<resStore.second.size(); i++) {
        cout<<resStore.second[i]<<" ";
    }
    return 0;
}

Answer 3

数组前 k 个元素（无相邻项）的最大和的递推关系 R(k) 是：

R(0) = 0, R(1) = max(0, a[0])
R(k) = max(a[k] + R(k-2), R(k-1))

这与您在代码中使用的循环几乎相同，但在您的代码中，您的函数 returns 是元素 k 及以后的最大总和。

无论如何，您可以使用动态规划在线性时间内构建这些值的 table。在伪代码中：

R = new array of length n+1
R[0] = 0
R[1] = max(0, a[0])
for i = 2 .. n
   R[i] = max(a[i-1] + R[i-2], R[i-1])

如果你只想要最大和，你可以returnR[n]。但是您也可以轻松地重建索引。在伪代码中：

indices(a, R):
    result = new empty vector
    i = n
    while i > 0
        if (i == 1 and a[0] > 0) or R[i] == a[i-1] + R[i-2]
            result.push_back(i-1)
            i -= 2
        else
            i -= 1

您必须反转 result 才能获得升序排列的索引。

选择的回溯值

backtrack value which were chosen

c++

algorithm

recursion

backtracking

array-algorithms