I'm trying to solve the knapsack problem in C code:

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.

I've tried a few different things, and posted here as well, but I still can't get the code to work correctly. Please help, thank you.

Here's the code I've got so far:

#include #include #include #include

typedef struct{ int weight; int value; char name[32]; } item_t;

void knapsack_search(int Lines,item_t *items,int *has_taken, int *solution, int capacity, int curr ent_weight, int current_value, int *highest_value) { printf("ks: %d, %d, %d, %d, %d, %d, %d ",Lines,*has_taken,*solution,capacity,current_weight,curre nt_value,*highest_value); if(current_value>*highest_value) { for(int i=0;i!=Lines;++i) { solution[i]=has_taken[i]; } *highest_value=current_value; } for(int index_to_try=0;index_to_try!=Lines;++index_to_try) { if(has_taken[index_to_try]) { continue; }

int new_weight = items[index_to_try].weight+current_weight; int new_value = items[index_to_try].value+current_value;

if(new_weight>capacity) { continue; } has_taken[index_to_try]=1; knapsack_search(Lines,items,has_taken,solution,capacity,new_weight,new_value,highest_value); has_taken[index_to_try]=0; } }

int solve_knapsack(int Lines,item_t *items,int *solution,int capacity) { printf("sk: %d, %d, %d ",Lines,*solution,capacity); int *has_taken=malloc(sizeof(int)*Lines); int highest_value=-1; memset(has_taken,0,sizeof(int)*Lines); knapsack_search(Lines,items,has_taken,solution,capacity,0,0,&highest_value); free(has_taken); return highest_value; }

int syntax_error(void) { fprintf(stderr,"Cannnot parse problem description "); return 3; }

int main(int argc, char *argv[]) { FILE *f; f=fopen("knapsack.data","r"); int capacity=0; int num=0; char n[128]; int i=0; int Lines=0; num=sscanf(argv[1],"%d",&capacity); printf("The capacity is: %d ",capacity); while(NULL != fgets(n,128,f)) { printf("Input line %d = %s ",++Lines,n); } item_t *items=malloc(sizeof(item_t)*Lines); for(i;i!=Lines;++i) { fscanf(f,"%d %d %s ",&items[i].value,&items[i].weight,items[i].name); } fclose(f); int *solution=malloc(sizeof(int)*Lines); int highest_value=solve_knapsack(Lines,items,solution,capacity); printf("You can carry goods with a value of %d. ",highest_value); for(int i=0;i!=Lines;++i) { if(solution[i]) { printf("%d, %d, %s ",items[i].value,items[i].weight,items[i].name); } } free(solution); free(items); }