Knapsack Problem and simulation of Knapsack 0/1 problem in c programming language

In this resource I explained the Knapsack problem and also simulation of Knapsack 0/1 problem is explained with the help of example.
At first understand the what is Knapsack problem, Knapsack problem says that the we select the items which weights is w(i). and total capacity is W, and the each items benefits is v(i). In knapsack problem we want to find the maximum benefits and total weights of selected items is less then or equals to the capacity( W).
Knapsack problem can be solved in two way’s 0/1 knapsack problem or Fractional Knapsack problem.
The fractional knapsack problem is solved using greedy method. 0/1 knapsack problem is solved using the dynamic programming.
Here I explained the 0/1 Knapsack problem.In 0/1 Knapsack problem we know that the it is solved using the dynamic programming.
In 0/1 Knapsack problem the item is either take item completely or not at all. Items cannot take in fractional amount.
This problem is solved using dynamic programming because of the dynamic programming gives the optimal solutions.

0/1 Knapsack problem is solved in four steps, which is as following:-

Step 1. In this step the problem is divided into the sub-problems means that the characterize the structure of an optimal solution. Each sub-problem is solved and keep track each items value.

Step 2. In this step the recursive solution is find. In this step optimal solution is step fist is defined recursively.

Step 3. In this step compute the cost of optimal solution. In knapsack problem cost is maximum benefits.
to calculate the cost is using the algorithm which is called 0/1 Knapsack Algorithm.
Step 4. In this step the find out the optimal solution. For finding the optimal solution we use the backtracking.

Implementation of 0/1 knapsack problem in c programming language is as:-
/* by www.computersciencearticle.in */
#include <conio.h>
#include <stdio.h>
void knapsack01(int v[],int w[],int n,int capacity)
{
int x=0,b[100][100],i=0;
for(x=0;x<=capacity;x++)
b[0][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];
}
}
printf("the matix isn");
for(i=0;i<=n;i++)
{
for(x=0;x<=capacity;x++)
printf("t%d",b[i][x]);
printf("n");
}
printf("the benifits is n%d",b[n][capacity]);
//actual
knapsackprintf("nthe selected items isn");
i=n,x=capacity;
while(i>0 && x>0)
{
if(b[i][x]!=b[i-1][x])
{printf("  %d",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;
}
}
}
// main function
void main()
{
int i,n,capacity,v[100],w[100];
clrscr();
printf("enter the total capacity of knapsack n");
scanf("%d",&capacity);
printf("enter the no of itemsn");
scanf("%d",&n);
//value of each item's
printf("enter the weight and value  of itemsn");
for(i=1;i<=n;i++)
scanf("%d %d",&w[i],&v[i]);
knapsack01(v,w,n,capacity);getch();
}
Lets take an example of 0/1 knapsack problem.

Question . Solve the 0/1 knapsack problem which capacity is 5 and total 5 items. each items weight and value( profits) is as following.
i1 (1,1)
i2 (2,6)
i3 (5,18)
i4 (6,22)
i5 (7,28).

Answer.

In given problem the W=5 and 5 items so the solution is as in given figure.

Output of 0/1 Knapsack problem

That is the maximum benefits is 18 and the selected items is third means i3.

One Response
  1. September 26, 2013