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.
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.
/* by www.computersciencearticle.in */
void knapsack01(int v,int w,int n,int capacity)
//set first column to zero
if( (v[i] b[i-1][x-w[i]] ) > b[i-1][x] )
b[i][x]= (v[i] b[i-1][x-w[i]] ) ;
printf("the matix isn");
printf("the benifits is n%d",b[n][capacity]);
knapsackprintf("nthe selected items isn");
while(i>0 && x>0)
// main function
printf("enter the total capacity of knapsack n");
printf("enter the no of itemsn");
//value of each item's
printf("enter the weight and value of itemsn");
Question . Solve the 0/1 knapsack problem which capacity is 5 and total 5 items. each items weight and value( profits) is as following.
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.