#include<iostream>

 using namespace std;
 
 
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
 
public:
	void print()
	{
    
	 for(int m=1;m<=n;m++)
   {
    cout<<bestx[m]<<" ";
   }
   cout<<endl;
	};
 
private:
  int Bound(int i);
  void Backtrack(int i);
 
  int c;//背包容量
  int n; //物品數
  int *w;//物品重量數組
  int *p;//物品價值數組
  int cw;//當前重量
  int cp;//當前價值
  int bestp;//當前最優值
  int *bestx;//當前最優解
  int *x;//當前解
 
};
 
 
int Knap::Bound(int i)
{
 //計算上界
	int cleft=c-cw;//剩余容量
	int b=cp;
	//以物品單位重量價值遞減序裝入物品
	while(i<=n&&w[i]<=cleft)
	{
	  cleft-=w[i];
	  b+=p[i];
	  i++;
	}
	//裝滿背包
	if(i<=n)
		b+=p[i]/w[i]*cleft;
	return b;
}
 
 
void Knap::Backtrack(int i)
{
  if(i>n)
  {
    if(bestp<cp)
	{     cout<<"最優解為"<<endl;
    	for(int j=1;j<=n;j++)
	    	 bestx[j]=x[j];
	    bestp=cp;
	}
	return;
  }
  if(cw+w[i]<=c) //搜索左子樹
  {             
      x[i]=1;
	  cw+=w[i];
	  cp+=p[i];
	  Backtrack(i+1);
	  cw-=w[i];
	  cp-=p[i];
  }
	  if(Bound(i+1)>bestp)//搜索右子樹
	  {
	      x[i]=0;
		  Backtrack(i+1);
	  }
  
}
 
 
class Object
{
 friend int Knapsack(int p[],int w[],int c,int n);
public:
	int operator<=(Object a)const
	{
	 return (d>=a.d);
	}

private:
	int ID;
	float d;
};
 
 
int Knapsack(int p[],int w[],int c,int n)
{
 //為Knap::Backtrack初始化
	int W=0;
	int P=0;
	int i=1;
	Object *Q=new Object[n];
	for(i=1;i<=n;i++)
	{
	 Q[i-1].ID=i;
	 Q[i-1].d=1.0*p[i]/w[i];
	 P+=p[i];
	 W+=w[i];
	}
	if(W<=c)
		return P;//裝入所有物品
	//依物品單位重量排序
	float f;
	for( i=0;i<n;i++)
	 for(int j=i;j<n;j++)
	 {
	  if(Q[i].d<Q[j].d)
	  {
	    f=Q[i].d;
		Q[i].d=Q[j].d;
		Q[j].d=f;
	  }
 
 
	 }
	
	Knap  K;
	K.p = new int[n+1];
    K.w = new int[n+1];
	K.x = new int[n+1];
	K.bestx = new int[n+1];
	K.x[0]=0;
	K.bestx[0]=0;
	for( i=1;i<=n;i++)
	{
	 K.p[i]=p[Q[i-1].ID];
	 K.w[i]=w[Q[i-1].ID];
	}
	K.cp=0;
	K.cw=0;
	K.c=c;
	K.n=n;
	K.bestp=0;
	//回溯搜索
	K.Backtrack(1);
    K.print();
    delete [] Q;
	delete [] K.w;
	delete [] K.p;
	return K.bestp;

}
 
void main()
{
	int *p;
	int *w;
    int c=0;
	int n=0;
	int i=0;
 
	cout<<"請輸入物品的個數："<<endl;
    cin>>n;
	p=new int[n+1];
	w=new int[n+1];
	p[0]=0;
	w[0]=0;
 
	cout<<"請輸入物品的價值："<<endl;
	for(i=1;i<=n;i++)
		cin>>p[i];
 
	cout<<"請輸入個物品的重量："<<endl;
	for(i=1;i<=n;i++)
		cin>>w[i];
 
	cout<<"請輸入背包容量："<<endl;
	cin>>c;
 
	cout<<Knapsack(p,w,c,n)<<endl;
    
}