Life Hacks

# Write a program to solve the Knapsack problem using greedy technique.

#include<iostream.h>

#include<conio.h>

void knapsack01(int v[ ], int w[ ], int n, int capacity)

{

int x = 0, b, i = 0;

for(x = 0; x <= capacity; x++)

b[x] = 0; //set first column to zero

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

{

for(x = 0; x <= capacity; x ++)

{

if(w[i] <= x)

{

if((v[i] b[i – 1][x – w[i]]) > b[i – 1][x])

{

b[i][x] = (v[i] b[i – 1][x – w[i]]);

}

else

{

b[i][x] = b[i – 1][x];

}

else

{

b[i][x] = b[i – 1][x];

}

}

}

cout << " \n The matrix is : ");

for(i = 0; i <= n; i ++)

{

for(x = 0; x <= capacity; x ++)

cout << b[i][x];

cout << " \n “;

}

cout << " \n The benifits is : " << b[n][capacity]; //actual knapsack

cout << " \n The selected items is : ";

i = n, x = capacity;

while(i > 0 && x > 0)

{

if(b[i][x] != b[i – 1][x])

{

cout << i;

b[i][x] = b[i – 1][x – w[i]];

x = x – w[i];

i = i – 1;

}

else

{

b[i][x] = b[i – 1][x];

i = i – 1;

}

}

}

void main( ) // main function

{

int i, n, capacity, v, w;

clrscr( );

cout << " enter the total capacity of knapsack ";

cin >> capacity;

cout << " enter the no of items ";

cin >> n; //value of each item’s

cout << " enter the weight and value of items ";

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

cin >> w[i] >> v[i];

knapsack01(v, w, n, capacity);

getch( );

}

Output:- 