Code Scrappers


Knapsack C Program


                  #include<stdio.h>
                  #include<stdlib.h>

                  int knapsack(int, int[], int[], int);

                  int max(int, int);

                  void main()

                  {
                          int n, W, i;

                          int weight[10], value[10];

                          printf("enter the no. of items\n");

                          scanf("%d",&n);

                          printf("enter the value and weight\n");

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

                          {
                                  scanf("%d%d",&value[i],&weight[i]);
                          }

                          printf("enter the capacity of knapsack\n");

                          scanf("%d",&W);

                          printf("%d",knapsack(W, weight, value, n));

                  }

                  int knapsack(int W, int weight[], int value[], int n)

                  {
                          if(n==0 || W==0)
                          {
                                  return 0;
                          }

                          else if(weight[n-1] > W)
                          {
                                  return knapsack(W, weight, value, n-1);
                          }
                          else
                          {
                                  return max(value[n-1] + knapsack(W-weight[n-1], weight, value, n-1), knapsack(W, weight, value, n-1));
                          }
                  }

                  int max(int a, int b)

                  {
                          if(a > b)
                          {
                                  return a;
                          }

                          else
                          {
                                  return b;
                          }
                  }




              



Output

          enter the no. of items
          3
          enter the value and weight
          100     20
          50      20
          180     5

          enter the capacity of knapsack : 70
          330