Monday, May 3, 2010

Implement 0/I Knapsack Problem using dynamic programming

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
16.#include ..iostream.h>
#include ..conio.h>
#include ..process.h>
const int max=30;

int MFKS(int,int);
int maximum(int,int);
int value[max];
int weight[max];
int v[max][max];
int x[max];
int N,M;

int MFKS(int i,int j)
{
int val;
if(v[i][j]==-1)
{
if(j..weight[i]) val=MFKS(i-1,j);
else val=maximum(MFKS(i-1,j),(MFKS(i-1,j-weight[i])+value[i]));
v[i][j]=val;
}
return v[i][j];
}

void svector()
{
int j1;
j1=M;
for(int i=N;i>=0;i--)
{
if(v[i][j1]!=v[i-1][j1])
{
x[i]=1;
j1=j1-weight[i];
}
}
for(i=1;i..=N;i++)
{
cout..."{";
for(i=1;i..=N;i++)
cout...x[i]...";";
cout..."}";
}
}

int maximum(int a,int b)
{
return (a>b)?a:b;
}


void main()
{
int optsol;
cout..."Enter no. of items:";
cin>>N;
cout..."Enter weights:\n";
for(int i=1;i..=N;i++)
cin>>weight[i];
cout..."Enter values:\n";
for(i=1;i..=N;i++)
cin>>value[i];
cout..."Enter Knapsack capacity:";
cin>>M;
for(i=0;i..=M;i++)
v[0][i]=0;
for(i=0;i..=N;i++)
v[i][0]=0;
for(i=1;i..=N;i++)
for(int j=1;j..=M;j++)
v[i][j]=-1;
optsol=MFKS(N,M);
cout..."Optimal solution = "...optsol...endl;
cout..."Optimal solution vector is:\n";
for(i=1;i..=N;i++)
x[i]=0;
svector();
cout...endl;
getch();
}







OUTPUT:

Enter no. of items: 4

Enter weights:
2 1 3 2

Enter values:
12 10 20 15

Enter Knapsack capacity:5
Optimal solution = 37
Optimal solution vector is:
{1; 1; 0; 1 ;}

No comments:

Post a Comment