Write an algorithm to solve knapsack problem using greedy technique.

Write an algorithm to solve the knapsack problem using greedy technique. Find the optimal solution to the knapsack instance n=7, m=15.

            (P1, P2, ………,P7) = (10,5,15,7,6,18,3)

            (W1,W2,…….,W7)=(2,3,5,7,1,4,1)

Answer:-

Algorithm:

void GreedyKnapsack(float m, int n)
// p[1:n] and w[1:n] contain the profits and weights
// respectively of the n objects ordered such that
// p[i]/w[i] >= p[i+1]/w[i+1]. m is the knapsack
// size and x[1:n] is the solution vector.

{
for (int i=1; i<=n; i++) x[i] = 0.0; // Initialize x. 

float U =m; 

for (i=1; i<=n; i++) { 

if (w[i] > U) break;
x[i] = 1.0;
U -= w[i];

}

if (i <= n) x[i] = U/w[i];

}