#include<iostream.h>

int c;	//背包容量
int n;	//物品數
int *w;	//物品重量
int *p;	//物品價值
int cw;	//當前重量
int cp;	//當前價值
int *choose;	//當前裝載情況
int bestp;	//最優價值
int *bestc;	//最優裝載情況


//回溯
void backtrack(int t)
{
	int i,j;
	if(t>n)
	{
		for(i=1;i<=n;i++)
		{
			cout<<choose[i]<<" ";
		}
		cout<<cw<<" ";
		cout<<cp<<endl;
		if(cp>bestp)
		{
			bestp=cp;
			for(j=1;j<=n;j++)
			{
				bestc[j]=choose[j];
			}
		}
	}
	else
	{
		for(i=0;i<=1;i++)
		{
			if(i==0)
			{
				choose[t]=0;
				backtrack(t+1);
			}
			if(i==1 && cw+w[t]<=c)
			{
				cw+=w[t];
				cp+=p[t];
				choose[t]=1;
				backtrack(t+1);
			}
		}
	}
	cw-=w[t-1]*choose[t-1];
	cp-=p[t-1]*choose[t-1];
}


//貪心，不能解決的問題
void greedy()
{


	int index=1,max=0;
	int *temp;
	temp=new int[n+1];
	for(int i=1;i<=n;i++)
	{
		choose[i]=0;
		cw=0;
		cp=0;
	}
	for(int j=1;j<=n;j++)
	{
		for(i=1;i<=n;i++)
		{
			if(((float)p[j]/w[j])<((float)p[i]/w[i]))
			{
				index++;
			}

		}
		temp[j]=index;
		index=1;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(temp[j]==i)
			{
				if(w[j]<c)
				{
					choose[j]=1;
					c-=w[j];
					cw+=w[j];
					cp+=p[j];
				}
			}
		}
	}
	
	bestp=cp;
	for(i=1;i<=n;i++)
	{
		bestc[i]=choose[i];
	}
}

int main()
{
	int i;

	cout<<"輸入背包容量:";
	cin>>c;
	cout<<"輸入物品數:";
	cin>>n;
	w=new int[n+1];
	p=new int[n+1];
	choose=new int[n+1];
	bestc=new int[n+1];
	cout<<"輸入各物品重量:";
	for(i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	cout<<"輸入各物品價值:";
	for(i=1;i<=n;i++)
	{
		cin>>p[i];
	}

	bestp=0;
	cw=0;
	cp=0;
	backtrack(1);

	cout<<"最優裝載："<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<bestc[i]<<" ";
	}
	cout<<bestp<<endl;
	return 0;
}



輸入背包容量:7
輸入物品數:4
輸入各物品重量:3 5 2 1
輸入各物品價值:9 10 7 4
0 0 0 0 0 0
0 0 0 1 1 4
0 0 1 0 2 7
0 0 1 1 3 11
0 1 0 0 5 10
0 1 0 1 6 14
0 1 1 0 7 17
1 0 0 0 3 9
1 0 0 1 4 13
1 0 1 0 5 16
1 0 1 1 6 20
最優裝載：
1 0 1 1 20


輸入背包容量:10
輸入物品數:5
輸入各物品重量:2 2 6 5 4
輸入各物品價值:6 3 5 4 6
0 0 0 0 0 0 0
0 0 0 0 1 4 6
0 0 0 1 0 5 4
0 0 0 1 1 9 10
0 0 1 0 0 6 5
0 0 1 0 1 10 11
0 1 0 0 0 2 3
0 1 0 0 1 6 9
0 1 0 1 0 7 7
0 1 1 0 0 8 8
1 0 0 0 0 2 6
1 0 0 0 1 6 12
1 0 0 1 0 7 10
1 0 1 0 0 8 11
1 1 0 0 0 4 9
1 1 0 0 1 8 15
1 1 0 1 0 9 13
1 1 1 0 0 10 14
最優裝載：
1 1 0 0 1 15