C Program: I need help with resolving the output which it does not sum the total value and weights of each item for knapsack exhaustive search? Total Weight should equal knapsack capacity of 26 and Total value should sum up based on the weight of each item that does not overexceed the knapsack capacity.

Text Files:

knapsack1_capacity.txt: 26

knapsack1_values.txt: 24,13,23,15,16

knapsack1_weights.txt: 12,7,11,8,9

knapsack1_optimal_selection.txt: 0,1,1,1,0

# include #include #include

struct Knapsack { int value; int weight; };

// returns maximum of two integers int max(int a, int b) { return (a > b)? a : b; } // Returns the maximum value that can be put in a knapsack of capacity W struct Knapsack knapSackExhaustive(int W, int wt[], int val[], int n){ int i, w; int K[n+1][W+1]; int totalWeight=0;

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++){ for (w = 0; w <= W; w++){ // base case if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w){ K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); } else K[i][w] = K[i-1][w]; } } //For calculation of totalweight; int res = K[n][W]; w = W; for (i = n; i > 0 && res > 0; i--) { // either the result comes from the top // (K[i-1][w]) or from (val[i-1] + K[i-1] // [w-wt[i-1]]) as in Knapsack table. If // it comes from the latter one/ it means // the item is included. if (res == K[i - 1][w]) continue; else { // This item is included. //printf("%d ", wt[i - 1]); totalWeight=totalWeight+wt[i-1]; // Since this weight is included its // value is deducted res = res - val[i - 1]; w = w - wt[i - 1]; } }

struct Knapsack knap; knap.value=K[n][W]; knap.weight=totalWeight; return knap; }// end struct knapSackExhaustive

int main(void) { struct Knapsack aSack; int i; time_t t; int val[5]={0}; int wt[5]={0}; //Intializes random number generator srand((unsigned) time(&t)); printf("Knapsack Brute Force "); // Print 5 random values FILE *fileValues; printf("Five Random Values: "); for( i = 0 ; i < 5 ; i++ ) val[i]=0; i=0; if((fileValues = fopen("knapsack1_values.txt", "r"))==NULL){ printf("knapsack1_values.txt failed to open "); return 1; } else while(fscanf(fileValues,"%d",&val[i])!=EOF){ printf("%d ",val[i]); i++; } // Print 5 random weights int j; FILE *fileWeights; printf("Five Random Weights: "); for( j = 0 ; j < 5 ; j++ ) wt[j]=0; j=0; if((fileWeights = fopen("knapsack1_weights.txt", "r"))==NULL){ printf("knapsack1_weights.txt failed to open "); return 1; } else while(fscanf(fileWeights,"%d",&wt[j])!=EOF){ printf("%d ",wt[j]); j++; }

printf("Knapsack Capacity: "); int W; FILE *fileCapacity; fileCapacity = fopen("knapsack1_capacity.txt", "r"); if (fileCapacity) { while ((W = getc(fileCapacity)) != EOF) putchar(W); fclose(fileCapacity); }

int n = sizeof(val)/sizeof(val[0]); aSack = knapSackExhaustive(W, wt, val, n); // Total Value and Weight for the items chosen to put into the Knapsack printf("Total Value: %d\t ", aSack.value); printf("Total Weight:%d\t ",aSack.weight); printf("Optimal Selection of the item's weights: "); int O ; FILE *fileOptimalSelection; fileOptimalSelection = fopen("knapsack1_optimal_selection.txt", "r"); if (fileOptimalSelection) { while ((O = getc(fileOptimalSelection)) != EOF) putchar(O); fclose(fileOptimalSelection); } return 0; }