ダイナミックプログラミングAltogorithm

Question

Iは、次の入力/質問とO（NB）の時間で実行するアルゴリズムを構築しようとしている： 入力：n個の異なる整数および整数bのアレイAが[1..nの]を（私は、Aの数字がnで終わる1、すなわちn = 4 A [1,2,3,4]で始まると仮定しています。 質問：要素の合計として何通り書けますか？ A []内の要素を1回しか使用できない場合の配列の文字列を返すのですか？

私はいくつかの再帰的な解決方法を探していますが、たとえば、1で始まって1つ（ちょうど1つ）、次に2つ（ちょうど2つ）、そして3つ（または2 + 1）などのすべての方法を保存した場合、それは難しいはずはありませんどのように多くの方法を見て大きな数字を作ることができます。しかし、例えば5を取った場合、4 + 1に分解することができ、4をさらに3 + 1に分解することができるので、2つの解（4 + 1、3 + 1 + 1）が、そのうちの1つに番号の繰り返しがあります。私は明白な何かを欠いていますか本当にありがとう！

Answer 1

レッツF（X、I）Aの方法の要素の数である[1：i]はXを得るために加算することができます。

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

これです！すなわち、6のために、それは3 + 2 + 1を見つけられないでしょう

私は何かが足りないかもしれない

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を渡すことによってのみ関数定義を変更する必要があります。終了のため

ケース[下界] + ARR ARR [は、UpperBound] ==コメント

に基づいて

編集bはあなたが整数ナップサックの修正バージョンを使用する必要があります場合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でも参照。