knapsack_dynamic

 #include<stdio.h>

int max(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 val[100],wt[100];

  int W,n;

  printf("Enter the number of items: ");

  scanf("%d",&n);

  printf("Enter the values and weights of %d items:\n",n);

  for(int i=0;i<n;i++){

    printf("Enter value and weight for item %d:",i+1);

    scanf("%d%d",&val[i],&wt[i]);

  }

  printf("Enter the knapsack capacity: ");

  scanf("%d",&W);

  printf("Max value: %d\n",knapsack(W,wt,val,n));

  return 0;

}