# C Program to solve Knapsack problem

C Program to solve Knapsack problem. Knapsack problem is also called as rucksack problem. In Knapsack problem, given a set items with values and weights and a limited weight bag . We have to find the optimum solution so that, in minimum cost(value) fill the bag with the maximum weight. Read more about C Programming Language .

`/************************************************************ You can use all the programs on  www.c-program-example.com* for personal and learning purposes. For permissions to use the* programs for commercial purposes,* contact [email protected]* To find more C programs, do visit www.c-program-example.com* and browse!* *                      Happy Coding***********************************************************/#include<stdio.h>#include<conio.h>int w[10],p[10],v[10][10],n,i,j,cap,x[10]={0};int max(int i,int j){ return ((i>j)?i:j);}int knap(int i,int j){ int value; if(v[i][j]<0) {  if(j<w[i])   value=knap(i-1,j);  else   value=max(knap(i-1,j),p[i]+knap(i-1,j-w[i]));  v[i][j]=value; } return(v[i][j]);}void main(){ int profit,count=0; clrscr(); printf("nEnter the number of elementsn"); scanf("%d",&n); printf("Enter the profit and weights of the elementsn"); for(i=1;i<=n;i++) {  printf("For item no %dn",i);  scanf("%d%d",&p[i],&w[i]); } printf("nEnter the capacity n"); scanf("%d",&cap); for(i=0;i<=n;i++)  for(j=0;j<=cap;j++)   if((i==0)||(j==0))    v[i][j]=0;   else    v[i][j]=-1; profit=knap(n,cap); i=n; j=cap; while(j!=0&&i!=0) {  if(v[i][j]!=v[i-1][j])  {   x[i]=1;   j=j-w[i];   i--;  }  else   i--; } printf("Items included aren"); printf("Sl.notweighttprofitn"); for(i=1;i<=n;i++)  if(x[i])   printf("%dt%dt%dn",++count,w[i],p[i]); printf("Total profit = %dn",profit); getch();}`
`Read more Similar C ProgramsData StructuresLearn C Programming`

You can easily select the code by double clicking on the code area above.