动态规划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。