Fractional knapsack for report
A draft report has five chapters. The table shows the lengths of the chapters & their importance where the scale is from 1(low) to 10(high). The report must be at most 600 pages long. The problem is to edit the report so that the overall importance is maximized. Implement the fractional knapsack algorithm using Greedy Programming.
Chapter Pages Importance 1 120 5 2 150 5 3 200 4 4 150 8 5 140 3
C++ Code
/* program to implement fractional knapsack problem using
greedy programming for a given report*/
#include<iostream>
using namespace std;
int main()
{
/* Array\'s first row is to store pages
second row is to store importance of that chapter */
int array[2][100]={{120,150,200,150,140},{5,5,4,8,3}},n=5,w=600,i,curw,used[100],maxi=-1,totalprofit=0;
cout<<"Number of chapters: "<<n<<"\n";
cout<<"Pages of the report: "<<w;
for(i=0;i<n;i++)
{
used[i]=0;
}
curw=w;
//loop until report is full
while(curw>=0)
{
maxi=-1;
//loop to find most importance chapter
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;
//add that chapter to report
curw-=array[0][maxi];
//increase report importance
totalprofit+=array[1][maxi];
if(curw>=0)
{
cout<<"\nAdded chapter "<<maxi+1<<" Pages: "<<array[0][maxi]<<" Importance: "<<array[1][maxi]<<" completely in the report, Pages left: "<<curw;
}
else
{
cout<<"\nAdded chapter "<<maxi+1<<" Pages: "<<array[0][maxi]<<" Importance: "<<array[1][maxi]<<" partially in the report, Pages left: 0"<<" Pages added is: "<<curw+array[0][maxi];
totalprofit-=array[1][maxi];
totalprofit+=(1+((float)curw/array[0][maxi])*array[1][maxi]);
}
}
cout<<"\nReport filled with pages of importance: "<<totalprofit;
return 0;
}
