動態規劃Altogorithm

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（3或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]，其中A [1] < = A [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 基本情況是，如果ARR [下界] + ARR [上界] == b

基於評論

編輯您將需要使用整數揹包的修改版本問題。 [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。