# 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, n, w, i, curw, used, 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[i] >> array[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[i]`
32. `                    / (float) array[i]) > ((float) array[maxi]`
33. `                    / (float) array[maxi]))))`
34. `            {`
35. `                maxi = i;`
36. `            }`
37. `        }`
38. `        used[maxi] = 1;`
39. `        //decrease current wight`
40. `        curw -= array[maxi];`
41. `        //increase total profit`
42. `        totalprofit += array[maxi];`
43. `        if (curw >= 0)`
44. `        {`
45. `            cout << "\nAdded object " << maxi + 1 << " Weight: "`
46. `                    << array[maxi] << " Profit: " << array[maxi]`
47. `                    << " completely in the bag, Space left: " << curw;`
48. `        }`
49. `        else`
50. `        {`
51. `            cout << "\nAdded object " << maxi + 1 << " Weight: "`
52. `                    << (array[maxi] + curw) << " Profit: "`
53. `                    << (array[maxi] / array[maxi]) * (array[maxi]`
54. `                            + curw) << " partially in the bag, Space left: 0"`
55. `                    << " Weight added is: " << curw + array[maxi];`
56. `            totalprofit -= array[maxi];`
57. `            totalprofit += ((array[maxi] / array[maxi]) * (array[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.

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