by greedy method :
always try to fill the knapsack with job havin highest p/w ratio at each
time
p/w={ 5 ,1.66 ,3 , 1
,18 , .75 ,2 }
sort objects according to their p/w ratio {18 ,10 , 15. 2, 5, 7, 3 }
{ 1 , 2 ,5 ,
1, 3, 7, 4 }
1+2+5+1+3+7=19
overflow
optimal solution is w= 1+2+5+1+3=12
profit= 18+10+15+2+5=50
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
