使用二维数组的未处理的异常错误

Question

此动态编程算法正在返回未处理的异常错误，可能是由于我用于各种（和非常多）输入数量的二维数组。我似乎无法弄清楚这个问题。完整的程序如下：

// A Dynamic Programming based solution for 0-1 Knapsack problem 
#include<stdio.h> 
#include<stdlib.h> 
#define MAX 10000 


int size; 
int Weight; 
int p[MAX]; 
int w[MAX]; 

// A utility function that returns maximum of two integers 
int maximum(int a, int b) { return (a > b) ? a : b; } 

// Returns the maximum value that can be put in a knapsack of capacity W 
int knapSack(int W, int wt[], int val[], int n) 
{ 
int i, w; 
int retVal; 
int **K; 
K = (int**)calloc(n+1, sizeof(int*)); 
for (i = 0; i < n + 1; ++i) 
{ 
    K[i] = (int*)calloc(W + 1, sizeof(int)); 
} 

// Build table K[][] in bottom up manner 
for (i = 0; i <= n; i++) 
{ 
    for (w = 0; w <= W; w++) 
     { 
    if (i == 0 || w == 0) 
     K[i][w] = 0; 

      else if (wt[i - 1] <= w) 
     K[i][w] = maximum(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 

      else 
      K[i][w] = K[i - 1][w]; 
    } 
} 

retVal = K[n][W]; 
for (i = 0; i < size + 1; i++) 
    free(K[i]); 
free(K); 
return retVal; 
} 

int random_in_range(unsigned int min, unsigned int max) 
{ 
int base_random = rand(); 
if (RAND_MAX == base_random) return random_in_range(min, max); 

int range = max - min, 
    remainder = RAND_MAX % range, 
    bucket = RAND_MAX/range; 

if (base_random < RAND_MAX - remainder) { 
    return min + base_random/bucket; 
} 
else { 
    return random_in_range(min, max); 
} 
} 

int main() 
{ 
srand(time(NULL)); 
int val = 0; 
int i, j; 
//each input set is contained in an array 
int batch[] = { 10, 20, 30, 40, 50, 5000, 10000 }; 
int sizeOfBatch = sizeof(batch)/sizeof(batch[0]); 
//algorithms are called per size of the input array 
for (i = 0; i < sizeOfBatch; i++){ 

    printf("\n"); 
    //dynamic array allocation (variable length to avoid stack overflow 
    //calloc is used to avoid garbage values 
    int *p = (int*)calloc(batch[i], sizeof(int)); 
    int *w = (int*)calloc(batch[i], sizeof(int)); 
    for (j = 0; j < batch[i]; j++){ 
     p[j] = random_in_range(1, 500); 
     w[j] = random_in_range(1, 100); 
    } 
    size = batch[i]; 
    Weight = batch[i] * 25; 

    printf("| %d ", batch[i]); 
    printf(" %d", knapSack(Weight, w, p, size)); 

    free(p); 
    free(w); 

} 

_getch(); 
return 0; 
} 

Answer 1

更改此：

for (i = 0; i < size + 1; i++) 
    free(K[i]); 
free(K); 
return K[size][Weight]; 

要这样：

int retVal; 
... 
retVal = K[size][Weight]; 
for (i = 0; i < size + 1; i++) 
    free(K[i]); 
free(K); 
return retVal;