c - 大输入背包算法

Question

我根据维基百科上的伪代码开发了这个背包算法。它适用于少量项目和容量(n=6，v=2014)，但它会崩溃大量(n=5，v=123456789)。

另一个问题是，我的程序是通过 makefile 测试的，时间限制设置为 1 秒。

我该怎么做才能节省时间和内存？

v - 背包容量
n - 项目数
权重[] - 权重
值[] - 值

int knapSack(int v, int weight[], int value[], int n){
    int a, i, j;

    int **ks;
    ks = (int **)calloc(n+1, sizeof(int*));

    for(a = 0; a < (n+1); a++) {
        ks[a] = (int *)calloc(v+1, sizeof(int));
    }

    for (i = 1; i <= n; i++){
        for (j = 0; j <= v; j++){
            if (weight[i-1] <= j){
                ks[i][j] = max(value[i-1] + ks[i-1][j-weight[i-1]],  ks[i-1][j]);
            } else {
                ks[i][j] = ks[i-1][j];
            }
        }
    }

    int result = ks[n][v];

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

    return result;
}

Answer 1

在堆栈上声明的包含 123456789 个整数元素的数组将使许多 C 实现崩溃。听起来这就是您的问题。您是否在函数内部(在堆栈上)声明了数组？

// on heap
static int v[123456789]={0};

// on the stack (inside a function like main() )
int foo()
{
  int v[123456789]={0};
}