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[10] = {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[10] = {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[10];
  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.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.