$ 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
Users Online
· Guests Online: 33
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Newest Threads
No Threads created
Hottest Threads
No Threads created
Latest Articles
Articles Hierarchy
C++ Program to Solve the Fractional Knapsack Problem
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.
-
/* program to implement fractional knapsack problem using greedy programming */
-
#include<iostream>
-
using namespace std;
-
int main()
-
{
-
int array[2][100], n, w, i, curw, used[100], maxi = -1, totalprofit = 0;
-
//input number of objects
-
cout << "Enter number of objects: ";
-
cin >> n;
-
//input max weight of knapsack
-
cout << "Enter the weight of the knapsack: ";
-
cin >> w;
-
/* Array's first row is to store weights
-
second row is to store profits */
-
for (i = 0; i < n; i++)
-
{
-
cin >> array[0][i] >> array[1][i];
-
}
-
for (i = 0; i < n; i++)
-
{
-
used[i] = 0;
-
}
-
curw = w;
-
//loop until knapsack is full
-
while (curw >= 0)
-
{
-
maxi = -1;
-
//loop to find max profit object
-
for (i = 0; i < n; i++)
-
{
-
if ((used[i] == 0) && ((maxi == -1) || (((float) array[1][i]
-
/ (float) array[0][i]) > ((float) array[1][maxi]
-
/ (float) array[0][maxi]))))
-
{
-
maxi = i;
-
}
-
}
-
used[maxi] = 1;
-
//decrease current wight
-
curw -= array[0][maxi];
-
//increase total profit
-
totalprofit += array[1][maxi];
-
if (curw >= 0)
-
{
-
cout << "\nAdded object " << maxi + 1 << " Weight: "
-
<< array[0][maxi] << " Profit: " << array[1][maxi]
-
<< " completely in the bag, Space left: " << curw;
-
}
-
else
-
{
-
cout << "\nAdded object " << maxi + 1 << " Weight: "
-
<< (array[0][maxi] + curw) << " Profit: "
-
<< (array[1][maxi] / array[0][maxi]) * (array[0][maxi]
-
+ curw) << " partially in the bag, Space left: 0"
-
<< " Weight added is: " << curw + array[0][maxi];
-
totalprofit -= array[1][maxi];
-
totalprofit += ((array[1][maxi] / array[0][maxi]) * (array[0][maxi]
-
+ curw));
-
}
-
}
-
//print total worth of objects filled in knapsack
-
cout << "\nBags filled with objects worth: " << totalprofit;
-
return 0;
-
}
Output:
Comments
No Comments have been Posted.
Post Comment
Please Login to Post a Comment.