# C Program to Solve the Fractional Knapsack Problem

«
»
This is a C Program to solve fractional knapsack problem. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Here is the source code of the C program to solve fractional knapsack problem. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h>`
2. ` `
3. `int n = 5; /* The number of objects */`
4. `int c = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what`
5. `                YOU PAY to take the object */`
6. `int v = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.`
7. `                what YOU GET for taking the object */`
8. `int W = 15; /* The maximum weight you can take */`
9. ` `
10. `void simple_fill() {`
11. `    int cur_w;`
12. `    float tot_v;`
13. `    int i, maxi;`
14. `    int used;`
15. ` `
16. `    for (i = 0; i < n; ++i)`
17. `        used[i] = 0; /* I have not used the ith object yet */`
18. ` `
19. `    cur_w = W;`
20. `    while (cur_w > 0) { /* while there's still room*/`
21. `        /* Find the best object */`
22. `        maxi = -1;`
23. `        for (i = 0; i < n; ++i)`
24. `            if ((used[i] == 0) &&`
25. `                ((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))`
26. `                maxi = i;`
27. ` `
28. `        used[maxi] = 1; /* mark the maxi-th object as used */`
29. `        cur_w -= c[maxi]; /* with the object in the bag, I can carry less */`
30. `        tot_v += v[maxi];`
31. `        if (cur_w >= 0)`
32. `            printf("Added object %d (%d\$, %dKg) completely in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);`
33. `        else {`
34. `            printf("Added %d%% (%d\$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);`
35. `            tot_v -= v[maxi];`
36. `            tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];`
37. `        }`
38. `    }`
39. ` `
40. `    printf("Filled the bag with objects worth %.2f\$.\n", tot_v);`
41. `}`
42. ` `
43. `int main(int argc, char *argv[]) {`
44. `    simple_fill();`
45. ` `
46. `    return 0;`
47. `}`

```\$ gcc fractional_knapsack.c -o fractional_knapsack
\$ ./fractional_knapsack

Added object 5 (10\$, 4Kg) completely in the bag. Space left: 11.
Added object 2 (2\$, 1Kg) completely in the bag. Space left: 10.
Added object 3 (2\$, 2Kg) completely in the bag. Space left: 8.
Added object 4 (1\$, 1Kg) completely in the bag. Space left: 7.
Added 58% (4\$, 12Kg) of object 1 in the bag.
Filled the bag with objects worth 17.33\$.```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 