Изменение содержимого массива в рекурсивной функции

Question

У меня проблемы с пониманием рекурсии и массивов.

По сути, программа проверяет максимальный вес предметов, которые можно поместить в два поля. Я знаю, что это далеко не идеально, как сейчас, но это не главное.

Обычно все работает правильно, однако теперь я решил, что хочу видеть содержимое каждой коробки, когда вес максимален. Для этого я попытался использовать arr1 и arr2.

Я не понимаю, почему я получаю разные результаты для arr1 и arr2 (первый вариант дает мне то, что я хочу, второй - нет).

Это программа:

#define N 5
int help(int items[N][2], int box1[N], int box2[N], int rules[N][N], 
         int optimal,int current_weight,int item,int arr1[],int arr2[])
{
  if (item == N)
    {
      if(current_weight>optimal) //This is the first option
        {
          memcpy(arr1,box1,sizeof(int)*N);
          memcpy(arr2,box2,sizeof(int)*N);
        }
      return current_weight;
    }
  int k = items[item][1]; int sol;
  for (int i = 0; i <= k; i++)
    {
      for (int j = 0; i+j <= k; j++)
        {
          box1[item] += i; box2[item] += j;
          if (islegal(items, box1, box2, rules))
            {
              sol = help(items, box1, box2, rules, optimal, 
                   current_weight + (i + j)*items[item][0],item+1,arr1,arr2);
              if (sol > optimal)
                {
                  optimal = sol;
                  memcpy(arr1,box1,sizeof(int)*N); //This is the second option
                  memcpy(arr2,box2,sizeof(int)*N);
                }
            }
          box1[item] -= i; box2[item] -= j;
        }
    }
  return optimal;
}

int insert(int items[N][2], int rules[N][N])
{
  int box1[N] = { 0 }; int arr1[N] = { 0 };
  int box2[N] = { 0 }; int arr2[N] = { 0 };
  int optimal = 0;
  int x = help(items, box1, box2, rules,0, 0,0,arr1,arr2);
  print(arr1, N);
  print(arr2, N);
  return x;
}

Может кто-нибудь объяснить, что вызывает разницу? Почему первый вариант правильный, а второй нет? Я не мог понять это самостоятельно.

Большое спасибо.

Answer 1

Это не работает, потому что когда вы передаете box1 и box2 в помощь, они мутируют на help.Из алгоритма очевидно, что вы не хотите, чтобы они были видоизменены.Итак, мы можем сделать следующее:

int help(int items[N][2], int box1in[N], int box2in[N], int rules[N][N], 
         int optimal,int current_weight,int item,int arr1[],int arr2[])
{
    int box1[N];
    int box2[N];
    memcpy(box1, box1in, sizeof(int)*N);
    memcpy(box2, box2in, sizeof(int)*N);

Ваш алгоритм может все еще иметь проблемы, но эта проблема теперь устранена.