#include <iostream>
#include <iomanip>

using namespace std;

void Kanpsack(int *v,int *w,int c,int n,int m[][9])
{
for(int i=0;i<=c;i++)
{
m[0][i]=0;
}
for(int j=0;j<=n;j++)
{
m[j][0]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
if(j<w[i])
{
m[i][j]=m[i-1][j];
}
else
{
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
}
}
}
}

void Traceback(int m[][9],int *w,int c,int n,int *x)
{
for(int i=0;i<n;i++)
{
if(m[i][c]==m[i+1][c])
{
x[i]=0;
}
else
{
x[i]=1;
c-=w[i];
}
}
x[n]=(m[n][c])?1:0;
}

int main()
{
/**
int *v;
int *w;
int c;
int n;
int **m;*/
int n=4,c=8;
int w[5]={0,2,3,4,5};
int v[5]={0,3,4,5,6};
//int **m;
//m=new int *[5];
//for(int i=0;i<=4;i++)
//{
// m[i]=new int[9];
//}
int m[5][9];
int x[5];
Kanpsack(v,w,c,n,m);
Traceback(m,w,c,n,x);
for(int i=0;i<=n;i++)
{
cout<<x[i]<<' ';
}
return 0;
}