Program to implement knapsack problem using greedy method

//Program to implement knapsack problem using greedy method

What actually Problem Says ?

1. Given a set of items, each with a weight and a value.
2. Determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible.
3. It derives its name from the problem faced by someone who is constrained by afixed-size knapsack and must fill it with the most useful items.

Program :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

# include<stdio.h>   void knapsack(int n, float weight[], float profit[], float capacity) {    float x[20], tp = 0;    int i, j, u;    u = capacity;      for (i = 0; i < n; i++)       x[i] = 0.0;      for (i = 0; i < n; i++) {       if (weight[i] > u)          break;       else {          x[i] = 1.0;          tp = tp + profit[i];          u = u - weight[i];       }    }      if (i < n)       x[i] = u / weight[i];      tp = tp + (x[i] * profit[i]);      printf("\nThe result vector is:- ");    for (i = 0; i < n; i++)       printf("%f\t", x[i]);      printf("\nMaximum profit is:- %f", tp);   }   int main() {    float weight[20], profit[20], capacity;    int num, i, j;    float ratio[20], temp;      printf("\nEnter the no. of objects:- ");    scanf("%d", &num);      printf("\nEnter the wts and profits of each object:- ");    for (i = 0; i < num; i++) {       scanf("%f %f", &weight[i], &profit[i]);    }      printf("\nEnter the capacityacity of knapsack:- ");    scanf("%f", &capacity);      for (i = 0; i < num; i++) {       ratio[i] = profit[i] / weight[i];    }      for (i = 0; i < num; i++) {       for (j = i + 1; j < num; j++) {          if (ratio[i] < ratio[j]) {             temp = ratio[j];             ratio[j] = ratio[i];             ratio[i] = temp;               temp = weight[j];             weight[j] = weight[i];             weight[i] = temp;               temp = profit[j];             profit[j] = profit[i];             profit[i] = temp;          }       }    }      knapsack(num, weight, profit, capacity);    return(0); }

Output :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Enter the no. of objects:- 7   Enter the wts and profits of each object:- 2 10 3 5 5 15 7 7 1 6 4 18 1 3   Enter the capacity of knapsack:- 15   The result vector is:- 1.000000        1.000000        1.000000        1.000000     1.000000        0.666667        0.000000   Maximum profit is:- 55.333332