C Program: How do I write a Knapsack brute force algorithm for 24 items with 3 text files:

knapsack2_capacity.txt: 6404180

knapsack2_optimal_selection.txt:

1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1

knapsack2_values.txt:

825594 1677009 1676628 1523970 943972 97426 69666 1296457 1679693 1902996 1844992 1049289 1252836 1319836 953277 2067538 675367 853655 1826027 65731 901489 577243 466257 369261

knapsack2_weight.txt:

382745 799601 909247 729069 467902 44328 34610 698150 823460 903959 853665 551830 610856 670702 488960 951111 323046 446298 931161 31385 496951 264724 224916 169684

Code:

# 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; double total_time; int val[24];

//Intializes randomtime time_t t; srand((unsigned) time(&t)); clock_t start,end; start = clock(); printf("Knapsack Brute Force "); // Print 24 random values FILE *fileValues; fileValues = fopen("knapsack2_values.txt", "r"); printf("Twenty Four Random Values: "); // Condition for empty value file if(fileValues==NULL){ printf("Error "); exit(0); } // adding values to array for(i=0;i<24;i++){ fscanf(fileValues,"%d",&val[i]); } for(i=0;i<24;i++){ printf("%d ",val[i]); } fclose(fileValues); // Print 24 random weights int j; int wt[24]; FILE *fileWeights; fileWeights = fopen("knapsack2_weights.txt", "r"); printf(" Twenty Four Random Weights: "); // Condition for empty weight file if(fileWeights==NULL){ printf("Error "); exit(0); } // adding weights to array for(j=0;j<24;j++){ fscanf(fileWeights,"%d",&wt[j]); } for(j=0;j<24;j++){ printf("%d ",wt[j]); } fclose(fileValues); // Reading from Knapsack Capacity text file printf(" Knapsack Capacity: "); int W; FILE *fileCapacity; fileCapacity = fopen("knapsack2_capacity.txt", "r"); // Condition for empty weight file if(fileCapacity==NULL){ printf("Error "); exit(0); } fscanf(fileCapacity,"%d",&W); fclose(fileCapacity); printf("%d ",W); 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); // Read and print optimal selection of item's weights chosen that does not exceed knapsack capacity printf(" Optimal Selection of the item's weights that does not exceed item's weights: "); int O ; FILE *fileOptimalSelection; fileOptimalSelection = fopen("knapsack2_optimal_selection.txt", "r"); if (fileOptimalSelection) { while ((O = getc(fileOptimalSelection)) != EOF) putchar(O); fclose(fileOptimalSelection); } end = clock(); // time count stops total_time = ((double) (end - start)) / CLK_TCK; // calculate total execution time printf("Time taken for knapsack to execute:%f seconds",total_time); return 0; }