#include <stdio.h>
void readdata();
void search(int);
void checkmax();
void printresult();
int c, n;        //c： 背包容量；n：物品數
int w[100], v[100];       //w[i]、v[i]：第i件物品的重量和價值
int a[100];        //a數組存放當前解各物品選取情況
//a[i]=0表示不選第i件物品，a[i]=1表示選第i件物品
int sum_value=0;//當前總價值
int sum_weight=0;//當前總重量
int best_value=-1;//記錄最大價值
int best_bag[100];//記錄最優選擇的包
int main()
{
	readdata();       //讀入數據
	search(0);        //遞歸搜索
	printresult();
}

void search(int m)
{
	if(m>=n)
		checkmax();   //檢查當前解是否是可行解，若是則把它的價值與max比較
	else
	{
		if((sum_weight+w[m])<=c){
	sum_weight+=w[m];
	sum_value+=v[m];
	a[m]=1;       //不選第m件物品
	search(m+1);  //遞歸搜索下一件物品
	sum_weight-=w[m];
	sum_value-=v[m];
	}
	a[m]=0;       //選第m件物品
	search(m+1);  //遞歸搜索下一件物品
}
}


void checkmax()
{	                  
	if(sum_value>best_value)  {            //價值大于max
		best_value=sum_value;            //替換max
		for(int i=0;i<n;i++){
best_bag[i]=a[i];

		}
	}

}
void readdata()

{printf("輸入物品數");
scanf("%d",&n);
printf("輸入背包容量");
scanf("%d",&c);
printf("輸入物品的重量和價值");
int i;
for(i=0;i<n;i++)
scanf("%d%d",&w[i],&v[i]);   //讀入第i件物品重量和價值
}
void printresult()
{
			printf("選擇的背包為");
	for(int i=0;i<n;i++){
		if(1==best_bag[i])
			printf("%d ",i+1);
		
		}

	printf("\n最大價值%d",best_value);
}