#include<iostream.h> #include<conio.h> void main() { clrscr(); float n,m,loc,max,ps,temp,i,k; float x[100],v[100],p[100],w[100]; cout<<endl<<"-------- KNAPSACK Problem using Greedy Method --------"<<endl<<endl; cout<<"Enter Total No. of Objects = "; cin>>n; cout<<"Enter Capacity of Knapsack = "; cin>>m; cout<<endl<<endl; for(i=1;i<=n;i++) // INPUT :- Weight and Profit of Objects { cout<<"Enter Profit of Object "<<i<<" = "; cin>>p[i]; cout<<"Enter Weight of Object "<<i<<" = "; cin>>w[i]; v[i]=p[i]/w[i]; cout<<"Profit per unit of Object "<<i<<" is = "<<v[i]<<endl<<endl<<endl; x[i]=0.0; } for(ps=1;ps<=n-1;ps++) // SORTING the Values of Profit Per Unit --> v[i] { // using Selection Sort Algorithm max=v[ps]; loc=ps; for(k=ps+1;k<=n;k++) { if(max<v[k]) { max=v[k]; loc=k; } } temp=v[ps]; v[ps]=v[loc]; v[loc]=temp; temp=p[ps]; p[ps]=p[loc]; p[loc]=temp; temp=w[ps]; w[ps]=w[loc]; w[loc]=temp; } cout<<endl<<endl<<endl; cout<<"After Arranging the Objects :-"<<endl<<endl; for(i=1;i<=n;i++) { cout<<"Profit of Object "<<i<<" is = "<<p[i]<<endl; cout<<"Weight of Object "<<i<<" is = "<<w[i]<<endl; cout<<"Profit per unit of Object "<<i<<" is = "<<v[i]<<endl<<endl<<endl; } for(i=1;i<=n;i++) // Greedy Knapsack Algo to Find Fraction of Objects { if(w[i]>m) break; x[i]=1.0; m=m-w[i]; } if(i<=n) x[i]=m/w[i]; float TP=0, TW=0; for(i=1;i<=n;i++) { cout<<"Fraction of Object "<<i<<" is = "<<x[i]<<endl<<endl; TP=TP+(p[i]*x[i]); // Finding Total Profit, Total Weight TW=TW+(w[i]*x[i]); } cout<<endl<<"Optimal Solution :-"<<endl<<endl; cout<<"Total Profit = "<<TP<<endl; cout<<"Total Weight = "<<TW; getch(); }
Web Pages by Students |
ABC of C Language by Shailender Sharma |
Bootable Pen Drive by Avtar Singh |
e-Trash or e-Treasure ? by Pallavi Bagga |
Lakshya by Rabina Bagga |
OOPs Concepts by Navjot Kaur |
Fitness First by Ankush Rathore |
Information Systems by Kajal Gupta |
Quiz Contest in C++ by Rajnish Kumar |
Core Java (Tutorial) by Shyena |
C Language Q&A by Anmol Sharma |
HTML 5 Tutorial by Kishan Verma |