значение возврата, которое было выбрано - PullRequest
Новая
       24

значение возврата, которое было выбрано

0 голосов
/ 08 мая 2018

У меня есть программа на С ++, которая вычисляет максимум массива при условии, что нельзя взять два последовательных элемента массива. Например: 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.

Спасибо.

Ответы [ 3 ]

0 голосов
/ 08 мая 2018

Я думаю, что приведенный ниже код удовлетворит вашу потребность. 

#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;
}
0 голосов
/ 08 мая 2018

Рекуррентное отношение R (k) для максимальной суммы первых k элементов массива (без смежных терминов): 

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

Это почти то же самое повторение, которое вы используете в своем коде, но в вашем коде ваша функция возвращает максимальную сумму элементов k и более поздних.

В любом случае, вы можете построить таблицу этих значений за линейное время, используя динамическое программирование. В псевдокоде: 

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])

Если вы просто хотите получить максимальную сумму, вы можете вернуть R [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, чтобы получить индексы в возрастающем порядке.

0 голосов
/ 08 мая 2018

Это определенно не самое эффективное решение, но, вероятно, с наименьшими усилиями по реализации: 

#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

Демонстрация жизни на coliru

Таким образом, возвращаемое значение увеличивается на std::vector<int>, который содержит используемые индексы рядом с текущей суммой.

std::max() можно использовать, если я предоставлю подходящий (перегруженный) operator<() для std::pair<int, std::vector<int> >. Чтобы не усложнять ситуацию, я просто заменил std::max() на респ. состояние.

...