I've come up with the program below for the following question:

Implement the bottom-up dynamic programming algorithm for the knapsack problem. The program should read inputs from a file called data.txt, and the output will be written to screen, indicating the optimal subset(s).

What I have keeps outputting 55. I don't know why or where I'm going wrong. Could I get some help? Thank you!

#include #include

// 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 int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[n+1][W+1];

// Build table K[][] bottom up 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] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } }

return K[n][W]; }

int main() {

FILE *myFile; myFile=fopen("data.txt", "r");

int val[20]={0}; int wt[20]={0}; int W=80; //Set capacity to 80 int i; int n;

for(i=0;i

n = sizeof(val)/sizeof(val[0]); printf("%d", knapSack(W, wt, val, n));//prints out the maximum value fclose(myFile); return 0; }