KNAPSACK ALGORITHM BY GREEDY METHOD
Knapsack algorithm follows the greedy algorithm. Knapsack in simpler words means bag; the aim of this algorithm is to find the maximum value or maximum profit.
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Suppose, a person went to a shop with a bag of capacity 25kg, now in the shop, there are 6 various items along with price tags attached. Among those 6 items, he is free to choose as many items possible within 25kg, keeping weight and cost in mind, he will choose items in order to have maximum profit.
CRITERIA FOR FILLING THE KNAPSACK USING GREEDY
 Items are arranged in descending order of their values or cost. The object is to maximize the value.
 Items are arranged in ascending order of their weights. Objects are to maximize the number of items in the knapsack.
 Items are arranged in descending order of certain ratios Pi = Vi / W_{ }_{i} where V_{i} is a value of item I_{i } and W_{i} is the weight of item I_{i}.
ALGORITHM
StepI Repeat for i=1 to n

X[i]= 0
 W= Value
 V=0
StepII Repeat for i=1 to n through step 4.
StepIII If I[i]>W goto step7.
StepIV If W_{i}> W
StepV
StepVI Return V.
StepVII Exit.
We are given a knapsack of 60 kgs. Find the feasible solution for the following 5 items where cost and weight of every item are given in the following table of items, also find the total profit earned.
ITEMS 
I1 
I2 
I3 
I4 
I5 
COST 
30 
40 
45 
77 
90 
WEIGHT 
5

10 
15 
22 
25 
Find feasible solutions for the following table given.
Using the three criteria, the items are arranged in descending order of certain ratios, P_{i}= V_{i}/W_{i} where V_{i} is the value of item I_{i} and W_{i} is the criteria of the item I_{i}_{.}
Cost/Weight of every item= {30/5, 40/10, 45/15, 77/22, 90/25} = {6.0, 4.0,3.0,3.5,3.6}
Cost/ Weight arranged in descending order= {6.0, 4.0, 3.6,3.5,3.0}
ITEMS 
I1 
I2 
I5 
I4 
I5 
COST 
30 
40 
90 
77 
45 
WEIGHT 
5

10 
25 
22 
15

Let Net profit P=0. Taking the items sequentially unit, the knapsack is filled, W=60kg
Taking I1 , = 60 5*1 = 55
= 0+ 30* 1= 0+30 = 30
Taking I2, = 55 10*1= 45
= 30+40*1=70
Taking I5, = 4525*1=20
=70+90*1=160
Taking item I4, we see the item has weight 22kgs but knapsack requires only 20kgs. So a part of item I4 will be considered i.e, X= 20/22
Taking I4, = 2022*20/22= 0
= 160+ 77*20/22= 160+70= 230
Hence, the knapsack has been filled up fully and profit earned is 230.
COMPLEXITY
Here we see that the items are considered based on the ratio value/weight in descending order.
Sorting P, profit in descending order in any suitable sorting algorithm requires big O(n log n) again in the above algorithm. We see, that filling the knapsack requires Big O in n times and the loop runs for Big O(n time). So the time complexity becomes Big O(n log n).