C++ Program to Solve the Fractional Knapsack Problem

This is a C++ Program to solve fractional knapsack. 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 source code of the C++ Program to Solve the Fractional Knapsack Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* program to implement fractional knapsack problem using greedy programming */
  2. #include<iostream>
  3. using namespace std;
  4. int main()
  5. {
  6.     int array[2][100], n, w, i, curw, used[100], maxi = -1, totalprofit = 0;
  7.     //input number of objects
  8.     cout << "Enter number of objects: ";
  9.     cin >> n;
  10.     //input max weight of knapsack
  11.     cout << "Enter the weight of the knapsack: ";
  12.     cin >> w;
  13.     /* Array's first row is to store weights
  14.      second row is to store profits */
  15.     for (i = 0; i < n; i++)
  16.     {
  17.         cin >> array[0][i] >> array[1][i];
  18.     }
  19.     for (i = 0; i < n; i++)
  20.     {
  21.         used[i] = 0;
  22.     }
  23.     curw = w;
  24.     //loop until knapsack is full
  25.     while (curw >= 0)
  26.     {
  27.         maxi = -1;
  28.         //loop to find max profit object
  29.         for (i = 0; i < n; i++)
  30.         {
  31.             if ((used[i] == 0) && ((maxi == -1) || (((float) array[1][i]
  32.                     / (float) array[0][i]) > ((float) array[1][maxi]
  33.                     / (float) array[0][maxi]))))
  34.             {
  35.                 maxi = i;
  36.             }
  37.         }
  38.         used[maxi] = 1;
  39.         //decrease current wight
  40.         curw -= array[0][maxi];
  41.         //increase total profit
  42.         totalprofit += array[1][maxi];
  43.         if (curw >= 0)
  44.         {
  45.             cout << "\nAdded object " << maxi + 1 << " Weight: "
  46.                     << array[0][maxi] << " Profit: " << array[1][maxi]
  47.                     << " completely in the bag, Space left: " << curw;
  48.         }
  49.         else
  50.         {
  51.             cout << "\nAdded object " << maxi + 1 << " Weight: "
  52.                     << (array[0][maxi] + curw) << " Profit: "
  53.                     << (array[1][maxi] / array[0][maxi]) * (array[0][maxi]
  54.                             + curw) << " partially in the bag, Space left: 0"
  55.                     << " Weight added is: " << curw + array[0][maxi];
  56.             totalprofit -= array[1][maxi];
  57.             totalprofit += ((array[1][maxi] / array[0][maxi]) * (array[0][maxi]
  58.                     + curw));
  59.         }
  60.     }
  61.     //print total worth of objects filled in knapsack
  62.     cout << "\nBags filled with objects worth: " << totalprofit;
  63.     return 0;
  64. }

Output:

$ g++ FractionalKnapsack.cpp
$ a.out
 
Enter number of objects: 3
Enter the weight of the knapsack: 50
10 60
20 100
30 120
 
Added object 1 Weight: 10 Profit: 60 completely in the bag, Space left: 40
Added object 2 Weight: 20 Profit: 100 completely in the bag, Space left: 20
Added object 3 Weight: 20 Profit: 80 partially in the bag, Space left: 0 Weight added is: 20
Bags filled with objects worth: 240

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

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.