I am currently working on a project where I write the dynamic algorithm and recursive algorithm for the Knapsack problem. I need to compare the times of how long each algorithm takes to run. I'm a bit stuck on how to do this.. Here is what I have tried so far and am currently doing:
for Ex here is my dynamic algorithim :int dynamic(int value[], int weight[], int n, int w){
// create arrray
//value per weight too optimize
//2d matrix
int matrix[n+1][w+1];
for(int i = 0; i <=n; i++){
for(int x = 0; x<=w; x++){
matrix[i][x] = 0;
}
}
for(int itemIndex = 1; itemIndex<=n; itemIndex++) {
for(int weightIndex = 1; weightIndex<=w; weightIndex++){
int currentValue = matrix[itemIndex - 1][weightIndex];
int itemWeight = weight[itemIndex - 1];
int potentValue = 0;
if(itemWeight <= weightIndex) {
potentValue = value[itemIndex - 1];
int weightLeft = weightIndex - itemWeight;
potentValue += matrix[itemIndex -1][weightLeft];
}
matrix[itemIndex][weightIndex] = max(potentValue, currentValue);
}
}
return matrix[n][w];
}
I then have a random function that randmozies a bunch of things inside my program so I do all of the time functunatily in here as well. here is what it looks like :
clock_t StartTime = clock();
recursive(vals, wts, n, w);
clock_t EndTime = clock();
cout << "Time for dynamic: " << (float)(EndTime- StartTime)/ CLOCKS_PER_SEC / << endl;
// recursive(vals, wts, n, w);
I get an output of 0 for each algorithim. Should I be calling time inside of each algorithm itself?
Aucun commentaire:
Enregistrer un commentaire