ruhul0

Knapsack - Algorithm

Jun 28th, 2016
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.73 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. struct data
  4. {
  5.     char name;
  6.     int weight,price;
  7. }element[5];
  8. int main()
  9. {
  10.     int i=0,j,temp,cap,n,w=0;
  11.     float ratio[5],tmp1;
  12.     char tmp;
  13.     scanf("%d",&n);
  14.     printf("Enter capacity:\n");
  15.     scanf("%d",&cap);
  16.     for(i=0;i<n;i++)
  17.     {
  18.         printf("Enter weight:\n");
  19.         scanf("%d",&element[i].weight);
  20.         printf("Enter price:\n");
  21.         scanf("%d",&element[i].price);
  22.         printf("Enter name:\n");
  23.         fflush(stdin);
  24.         scanf("%c",&element[i].name);
  25.  
  26.     }
  27.     for(i=0;i<n;i++)
  28.     {
  29.         ratio[i]=element[i].price/element[i].weight;
  30.     }
  31.     for (i = 0; i < n; i++)
  32.         {
  33.         for (j = i + 1; j <= n; j++)
  34.             {
  35.             if (ratio[i] < ratio[j])
  36.                 {
  37.                 tmp1 = ratio[j];
  38.                 ratio[j] = ratio[i];
  39.                 ratio[i] = tmp1;
  40.  
  41.                 temp = element[j].weight;
  42.                 element[j].weight = element[i].weight;
  43.                 element[i].weight = temp;
  44.  
  45.                 temp = element[j].price;
  46.                 element[j].price = element[i].price;
  47.                 element[i].price = temp;
  48.  
  49.                 tmp = element[j].name;
  50.                 element[j].name = element[i].name;
  51.                 element[i].name = tmp;
  52.                 }
  53.             }
  54.         }
  55.     i=0;
  56.      while (w<=cap)
  57.      {
  58.          if(element[i].weight<cap-w)
  59.          {
  60.              printf("Name: %c Weight: %d\n",element[i].name,element[i].weight);
  61.              w=w+element[i].weight;
  62.              i++;
  63.          }
  64.          else
  65.          {
  66.              printf("Name: %c Over: %d\n",element[i].name,cap-w);
  67.              break;
  68.          }
  69.      }
  70.      getchar();
  71.      getchar();
  72. }
Add Comment
Please, Sign In to add comment