Алгоритм динамического программирования

Question

Я пытаюсь построить алгоритм, который выполняется за время O (nb) со следующим вводом / вопросом: вход: массив A [1..n] из n различных целых чисел и целое число b (я предполагаю, что числа в A являются последовательными, начиная с 1 и заканчивая на n, то есть для n = 4 A [1,2,3] , 4]. вопрос: во сколько способов можно записать b как сумму элементов массива, если элементы в A [] можно использовать только один раз?

Я воткнулся в стену на этом. Я ищу какое-то рекурсивное решение, но я не вижу, как избежать использования повторяющихся чисел. Как, например, если мы начали с 1 и сохранили все способы сделать один (только 1), затем 2 (просто 2), затем три (3 или 2 + 1) и т. Д., Не должно быть трудно увидеть, сколько способов мы можем сделать большие числа. Но если, например, мы возьмем 5, мы увидим, что его можно разбить на 4 + 1, а 4 можно еще раз разбить на 3 + 1, поэтому мы увидим 2 решения (4 + 1 и 3+ 1 + 1), но один из них имеет повторение числа. Я что-то упускаю из виду? Большое спасибо!

Answer 1

Рекурсивные и динамические решения в C:

#include <stddef.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned char uchar;
typedef unsigned int uint;

typedef struct tAddend
{
  struct tAddend* pPrev;
  uint Value;
} tAddend;

void findRecursiveSolution(uint n, uint maxAddend, tAddend* pPrevAddend)
{
  uint i;

  for (i = maxAddend; ; i--)
  {
    if (n == 0)
    {
      while (pPrevAddend != NULL)
      {
        printf("+%u", pPrevAddend->Value);
        pPrevAddend = pPrevAddend->pPrev;
      }
      printf("\n");
      return;
    }

    if (n >= i && i > 0)
    {
      tAddend a;
      a.pPrev = pPrevAddend;
      a.Value = i;
      findRecursiveSolution(n - i, i - 1, &a);
    }

    if (i <= 1)
    {
      break;
    }
  }
}

void printDynamicSolution(uchar** pTable, uint n, uint idx, uint sum, tAddend* pPrevAddend)
{
  uchar el = pTable[idx][sum];

  assert((el != 0) && (el != 5) && (el != 7));

  if (el & 2) // 2,3,6 - other(s)
  {
    printDynamicSolution(pTable,
                         n,
                         idx - 1,
                         sum,
                         pPrevAddend);
  }

  if (el & 4) // self + other(s)
  {
    tAddend a;
    a.pPrev = pPrevAddend;
    a.Value = idx + 1;

    printDynamicSolution(pTable,
                         n,
                         idx - 1,
                         sum - (idx + 1),
                         &a);
  }

  if (el & 1) // self, found a solution
  {
    tAddend a;
    a.pPrev = pPrevAddend;
    a.Value = idx + 1;

    pPrevAddend = &a;
    while (pPrevAddend != NULL)
    {
      printf("+%u", pPrevAddend->Value);
      pPrevAddend = pPrevAddend->pPrev;
    }
    printf("\n");
  }
}

void findDynamicSolution(uint n)
{
  uchar** table;
  uint i, j;

  if (n == 0)
  {
    return;
  }

  // Allocate the DP table

  table = malloc(sizeof(uchar*) * n);

  if (table == NULL)
  {
    printf("not enough memory\n");
    return;
  }

  for (i = 0; i < n; i++)
  {
    table[i] = malloc(n + 1);

    if (table[i] == NULL)
    {
      while (i > 0)
      {
        free(table[--i]);
      }

      free(table);
      printf("not enough memory\n");
      return;
    }
  }

  // Fill in the DP table

  for (i = 0; i < n; i++)
  {
    for (j = 0; j <= n; j++)
    {
      if (i == 0)
      {
        table[i][j] = (i + 1 == j); // self
      }
      else
      {
        table[i][j] = (i + 1 == j) + // self
          2 * (table[i - 1][j] != 0) + // other(s)
          4 * ((j >= i + 1) && (table[i - 1][j - (i + 1)] != 0)); // self + other(s)
      }
    }
  }

  printDynamicSolution(table, n, n - 1, n, NULL);

  for (i = 0; i < n; i++)
  {
    free(table[i]);
  }

  free(table);
}

int main(int argc, char** argv)
{
  uint n;

  if (argc != 2 || sscanf(argv[1], "%u", &n) != 1)
  {
    n = 10;
  }

  printf("Recursive Solution:\n");
  findRecursiveSolution(n, n, NULL);

  printf("\nDynamic Solution:\n");
  findDynamicSolution(n);

  return 0;
}

Вывод: для 10:

Recursive Solution:
+10
+1+9
+2+8
+3+7
+1+2+7
+4+6
+1+3+6
+1+4+5
+2+3+5
+1+2+3+4

Dynamic Solution:
+1+2+3+4
+2+3+5
+1+4+5
+1+3+6
+4+6
+1+2+7
+3+7
+2+8
+1+9
+10

См. Также по ideone .

Answer 2

Пусть F (x, i) - количество способов суммирования элементов A [1: i] для получения x.

F(x,i+1) = F(x-A[i+1],i) + F(x,i)

Вот и все!

Answer 3

Это не решение для динамического программирования.Нерекурсивна.Предположение, что arr сортируется в вашем случае, как [i .... j], где a [i] <= a [j] Это достаточно просто </p>

void summer(int[] arr, int n , int b)
{
    int lowerbound = 0;
    int upperbound = n-1;
    while (lowerbound < upperbound)
    {
         if(arr[lowerbound]+arr[upperbound] == b)
         {
              // print arr[lowerbound] and arr[upperbound]
              lowerbound++; upperbound--;
         }
         else if(arr[lowerbound]+arr[upperbound] < b)
              lowerbound++;
         else
              upperbound--;
    }

}

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

Случай для завершения все еще lowerbound < upperbound Базовый случай, если arr [lowerbound] + arr [upperbound] == b

Отредактировано на основе комментариев

Вам нужно будет использовать модифицированную версию задачи о целочисленном ранце.Значения [i, j] оба должны быть изменены соответствующим образом.У вас возникла проблема, потому что вы, скорее всего, не слишком корректируете свой i, соответственно увеличьте его, тогда они не будут повторяться так, как у вас.