Unbounded fractional knapsack problem in C++

Hello Learners, today we are going to learn a very interesting topic that is Unbounded fractional knapsack problem in C++. Before going to code first, we learn what is the problem in knapsack next we will build a small algorithm for it. And we will implement that algorithm in a c++ programming language, the topic is going to be very interesting.

The time complexity for this algorithm is: o(nlogn)

M=capacity of the bag.

P[i]=profit or value.

w[i]= weigth of the bag.

Algorithm:

for i=1 to n                                                          
  calculate profit/weight ratio.
sort objects in decresing order of 
profit/weigth ratio.
for i=1 to n 
 if(M>0 && w[i]<=M)
  M=M-w[i];
  P=P+P[i];
else break;
 if(M>0)
P=P+P[i](M/w[i]);

C++: Program Unbounded fractional knapsack problem

Let’s consider an example problem for this, Consider a bag of total weight 20 and there 3 objects which are to be placed in the bag the table is given below for the three objects withe their profit or value. find the maximum profit or value that is to be placed in the bag.

table:

object    obj1    obj2      obj3

profit     25        24          15

weight   18        15           10

Now we will input the above values, in the code and get the maximum profit or maximum value.

Code:

#include<iostream>
using namespace std;

float wt[20],pt[20],profit=0.0,y[20];
 int n,i,w,temp,j,u;
class fractional_knapsack
{
 public:
 void getdata()
 {
 cout<<"enter the max weight of the bag:"<<endl;
 cin>>w;
 cout<<"how many objects you want to store inside the bag:"<<endl;
 cin>>n;
 cout<<"enter the wt of the objects:\n";
  for(i=1;i<=n;i++)
  {
    cin>>wt[i];
  }
 cout<<"enter the profit of the objects:"<<endl;
  for(i=1;i<=n;i++)
   {
    cin>>pt[i];
   }
 }
 void sortdata()
{
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
  {
   if((pt[j]/wt[j])<(pt[j+1]/wt[j+1]))
   {
    temp=pt[j];
    pt[j]=pt[j+1];
    pt[j+1]=temp;
    temp=wt[j];
    wt[j]=wt[j+1];
    wt[j+1]=temp;
   }
  }
 }
}
 void calculation()
 {
  for(i=0;i<n;i++)
  y[i]=0.0;
  u=w;
   for(i=0;i<n;i++)
   {
    if(wt[i]>u)
    break;
    y[i]=1.0;
    u=u-wt[i];
   }
   if(i<n)
   y[i]=u/wt[i];
   for(i=0;i<n;i++)
   profit=profit+(pt[i]*y[i]);
}
 void displaydata()
 {
cout<<"-------------------------------------------\n";
cout<<"objectno  weigth profit\t\n";
cout<<"-----------------------------------------------\n";
   for(i=1;i<=n;i++)
   {
     cout<<i<<"\t"<<wt[i]<<"\t"<<pt[i]<<"\t"<<endl;
    }
cout<<"MAXIMUM PROFIT:"<<profit;
 }
};
int main()
{
  fractional_knapsack obj;
  obj.getdata();
  obj.sortdata();
  obj.calculation();
  obj.displaydata();
return 0;
}

Output:

enter the max weight of the bag:
20
how many objects you want to store inside the bag:
3
enter the wt of the objects:
18
15
10
enter the profit of the objects:
25
24
15
-------------------------------------------
objectno weigth profit 
-----------------------------------------------
1 15 24 
2 10 15 
3 18 25 
MAXIMUM PROFIT:31.5

Also read: Strong password (String problem) in C++

3 responses to “Unbounded fractional knapsack problem in C++”

  1. AKASH RANJAN - says:

    Great contents… Thanks…..

  2. Thrivikram says:

    It’s very useful… Thank you for this information

  3. L P SHREYA - says:

    Great content… Thank you… Keep posting

Leave a Reply

Your email address will not be published. Required fields are marked *