What's New-Given Below
technicalsymposium
technicalsymposium
technicalsymposium

Knapsack Program Coding

technical symposium

Training Info
Admissions Info
Courses Info
Scholarships Info

GATE Info
UPSC Info
Job Info
Materials Info
technical symposium
technical symposium
technical symposium

/* program to knapsack using dynamic programming*/
#include<stdio.h>
#define MAX(a,b) a>b?a:b
int v[20][20];
struct KNAP
{
char item[15];
int value;
int weight;
}bag[20];
void knap(int n,int W)
{
int i,j;
int t1,t2;
for(i=0;i<=n;i++)
v[i][0]=0; //making first col as zero
for(i=0;i<=W;i++)
v[0][i]=0; //making first row as zero
for(i=1;i<=n;i++)
for(j=1;j<=W;j++)
{
if(j<bag[i].weight)
v[i][j]=v[i-1][j];
else
{
t1= v[i-1][j];
t2=v[i-1][j-bag[i].weight]+bag[i].value;
v[i][j]=MAX(t1,t2);
}
}
printf("\n\n\t\tVALUE MATRIX\n\n\t");
for(i=0;i<=n;i++,printf("\n\t"))
for(j=0;j<=W;j++,printf("\t"))
printf("%d",v[i][j]);
}
void finditem(int n,int W)
{
int i,j;
printf("\n\n\t\tITEM IN THE BAG\n\n");
for(i=n,j=W;i!=0 && j!=0;i--)
{
if(v[i][j]!=v[i-1][j])
{
printf("\t%s",bag[i].item);
j=j-bag[i].weight;
}
}
}
void main()
{
int n,i,j,W;
clrscr();
printf("\n\n\t\tKNAPSACK PROBLEM USING DYNAMIC PROGRAMMING\n\n");
printf("\n\tEnter No. of Items : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
fflush(stdin);
printf("\n\tEnter the Item %d name : ",i);
scanf("%s",bag[i].item);
printf("\nEnter the Weight & Valus of %s : ",bag[i].item);
scanf("%d%d",&bag[i].weight,&bag[i].value);
}
printf("\n\n\t\tEnter the Knapsack Capacity : ");
scanf("%d",&W);
clrscr();
printf("\n\n\t\tINITIAL STATE OF THE PROBLEM\n");
printf("\n\titem\tweight\tvalue\n\n");
for(i=1;i<=n;i++)
printf("\t%s\t%d\t%d\n",bag[i].item,bag[i].weight,bag[i].value);
knap(n,W);
finditem(n,W);
getch();
}

Hosting by Yahoo!

About-Us    Contact-Us    Site-map

©copyright 2009 All rights are reserved to technicalsymposium.com