Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Greedy Knapsack
for i=1 to n //step1
compute pi/wi; //step2
// form 1 to n we have compute above code ---- O(n) (tim taken , since it runs n times)
sort objects in non- increasing order p/w; //step3
// if i have n objects and i have to sort them, then
best sorting algorithm (compasion base sorting algo) is merge sort. -- O(nlogn) (time take for merge sort)
for i=1 to n //step4
if(m>0 && wi<=m) //step5
m = m - wi; //step6
P = P + pi; //step7
else //step8
break; //step9
// for above code we have iterate from 1 to on sorted list -- O(n) (time taken)
if(m>0) //step10
P=P+ pi*(m/wi); //step11
// this step will take constantant time so -- O(1) (time taken)
SO we total time taken will be = O(n) + O(nlogn) + O(n) +O(1)
so time complexity will be = O(nlogn)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment