이 동적 프로그래밍 알고리즘은 다양하고 (매우 큰) 입력에 대해 사용하고있는 2 차원 배열로 인해 처리되지 않은 예외 오류를 반환합니다. 여기서 문제를 파악할 수는 없습니다. 전체 프로그램은 다음과 같이2 차원 배열에서 처리되지 않은 예외 오류가 발생했습니다.
for (i = 0; i < size + 1; i++)
free(K[i]);
free(K);
return K[size][Weight];
이 사람 :이
// 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;
}
(이 어떤 종류의 손상을 야기 할 가능성이 높습니다.) 이것은 문제를 야기 할 수있는 유일한 색인 작업 인 것 같습니다 :'K [i - 1] [j - w [i - 1]]', 'w [i - 1]'이 음수 일 때 발생할 수있다. –
언어 태그 추가 –
범위가 정확합니다. 입력 값이 작 으면 (예 : 100 미만) 프로그램이 올바르게 실행됩니다. 그러나 입력 크기가 5000 이상이되면이 메시지가 나타납니다 : –