동적 프로그래밍 Altogorithm

Question

다음 입력/질문을 사용하여 O (nb) 시간에 실행되는 알고리즘을 구성하려고합니다 : 입력 : n 개의 다른 정수와 정수 b의 배열 A [1..n] 나는 A의 숫자가 n에서 끝나는 1에서 시작하여 순차적이라고 가정하고있다. 즉, n = 4 A [1,2,3,4]이다. 질문 : 요소의 합으로 얼마나 많은 방법을 쓸 수 있는가? A []의 요소를 한 번만 사용할 수있는 경우 배열 배열을 반환합니다.

이 벽에 일종의 충돌이 있습니다. 재귀 솔루션을 찾고 있는데 어떻게해야할지 모르겠다. 반복 숫자를 사용하지 마십시오. 예를 들어, 우리가 1에서 시작하여 모든 방법을 저장하여 1 (단 1), 2 (단 2), 세 (또는 2 + 1) 등을 만들면 하드 우리가 얼마나 많은 방법을 보았는지 더 큰 숫자를 만들 수 있습니다. 그러나 예를 들어 5를 취하면 4 + 1로 나눌 수 있고 4는 3 + 1로 더 세분화 될 수 있음을 알 수 있습니다. 그러면 2 개의 솔루션 (4 + 1, 3+ 1 + 1), 그러나 그 중 하나는 숫자의 반복을 가진다. 나는 명백한 것을 놓치고 있는가? 정말 고마워!

Answer 1

F (x, i)를 A [1 : i]의 요소가 x를 얻기 위해 합계 될 수있는 방법의 수라고합시다.

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

그게 전부입니다!

Answer 2

동적 프로그래밍 솔루션이 아닙니다. 비 재귀 적. 같은 사건에 정렬됩니다 ARR 가정은 [내가 .... J]만큼 쉬운 곳에 [i]를 <는 [J]를 = 은

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를 전달하여 함수 정의 만 변경하면됩니다. 해지

케이스 [LOWERBOUND] + 편곡 [UPPERBOUND] ==

B는 의견

에 따라 편집 ARR 당신은 정수 배낭의 수정 된 버전을 사용할 필요가있는 경우 lowerbound < upperbound 자료의 경우는 아직 문제. [i, j]의 값은 그에 따라 수정되어야합니다. 당신은 아마도 당신의 신앙을 가장 신중하게 수정하지 않기 때문에 문제가 있습니다. 그에 따라 당신의 것을 늘리십시오. 그러면 당신이 가지고있는 것과 같은 반복이 아닙니다. C에서

Answer 3

재귀 동적 솔루션 :

#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에 참고.