Need help with the following assignment:

Details

Your program should be called "pa5" and should operate as follows:

• pa5 expects a single argument, which is the weight capacity of the knapsack e.g.

pa5 15 would run your program for a bag with a weight capacity of 15;

• your program should read the file knapsack.data from the current directory. This file should contain a set of weight/value/name triples, such as the following:

1 10 mouse

2 25 cellphone

5 40 tablet

7 100 laptop

In the above file, there are four items: a mouse with a weight of 1 and value of 10; a cellphone with a weight of 2 and value of 25; and so on.

• After reading knapsack.data and storing the data in arrays, you should call a function (I called this MaxVal(x) in class) for computing the maximum value that can be loaded into a

knapsack with a weight capacity of x. MaxVal(x) works by returning 0 if x <= 0, otherwise returning the maximum of (v0+MaxVal(x-w0), v1+MaxVal(x-w1), ..., Vn+MaxVal(x-wn)) where each (vi,wi) is the value and weight of item i, and the maximum is computed over all items where wi <= x (i.e. where item i can fit in a bag with capacity x). This is the algorithm that was discussed in class.

• In addition to printing the maximum possible value, you should print how many of each item should be put in the bag.
• Your program should operate efficiently by storing the value of each MaxVal(x) that is computed, and retrieving that value (max value and list of items) instead of computing it whenever possible.
• Your program should echo the contents of knapsack.data, and then print the maximum value that can be loaded in a knapsack of the given capacity (which was specified as the argument to "pa5").

Error Checking

Make sure you handle error conditions, including: no argument to the program; too many arguments to the program; invalid argument to the program; missing or invalid knapsack.data file; and so on.

Assumptions

You may assume a maximum of 128 items in the knapsack.data file, and a maximum bag capacity of 1024. You may assume a maximum length of 32 characters for the 3rd column of knapsack.data (the item name), and assume that the name contains no spaces.

Here's the code I have so far, I'm not exactly sure how to get the data from the file into the variables I'll need to move to the function. I'm also not sure if I'm passing the variables correctly:

#include #include

int MaxVal(int a,int b) { return(a>b)?a:b; }

int knapsack(int W,int wt[],int val[],int n) { int i,w; int K[n+1][W+1]; 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(int argc,char **argv) { int val[128]; char Words[128]; int Lines=0; char *wt=argv[1]; int W=50; int num; int weight; FILE *fp; fp=fopen("knapsack.data","r"); while(NULL != fgets(Words,128,fp)) { printf("Input line %d = %s ",++Lines,Words); } fclose(fp); weight=sscanf(argv[1],"%d",&num); if(argc==2) { printf("Weight: %d ",num); } int n=sizeof(val)/sizeof(val[0]); printf("Value=%d ",knapsack(W,weight,val,n)); return 0; }