#include<stdio.h>
#define N 100
void knapsack(int n,int c,int v[],int w[],int **m);
void traceback(int n,int c,int w[],int **m,int x[]);
int min(int x,int y);
int max(int x,int y);
void main()
{   int w[N],v[N],x[N],n,c,k,**m;
	

	  printf("請輸入物品數：");
       scanf("%d",&n);
	   printf("\n請輸入容量：");
	   scanf("%d",&c);
	   printf("\n請輸入各物品的重量:");
	   for (k=1;k<=n;k++)
	   {
		  scanf("%d",&w[k]);
	   }
	   printf("請輸入各物品的價值：");
	   for(k=1;k<=n;k++)
	   {
		  scanf("%d",&v[k]);
	   }
	   m=new int *[n];
	   for(k=1;k<=n;k++)
	   { m[k]=new int[c];}
       knapsack(n,c,v,w,m);
        traceback(n,c,w,m,x);
		printf("選中的物品: ");
	    for (k=1;k<=n;k++)
		{	if(x[k]==1)
		   printf("%d號  ",k);
		}
      printf("\n");
	 printf("總的價值：%d\n",m[1][c]);
	
	
	

}
void knapsack(int n,int c,int v[],int w[],int **m)
{   int jmax,j,i;
     jmax=min(w[n]-1,c);
     for(j=0;j<=jmax;j++)
		 m[n][j]=0;
	 for(j=w[n];j<=c;j++)
         m[n][j]=v[n];
	 for(i=n-1;i>1;i--)
     {
		 jmax=min(w[i]-1,c);
         for(j=0;j<=jmax;j++)
          m[i][j]=m[i+1][j];
		 for(j=w[i];j<=c;j++)
           m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
     } 		 
	 m[1][c]=m[2][c];
	 if(c>=w[1])
     m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}


void traceback(int n,int c,int w[],int **m,int x[])
{ 
	int i;
	for(i=1;i<n;i++)
	{  if(m[i][c]==m[i+1][c]) { x[i]=0;  printf("(%d,%d):%d ",i,c,m[i][c]);}	
       else
	   { x[i]=1;
        printf("(%d,%d):%d ",i,c,m[i][c]);
	     c-=w[i];
	   }
	     x[n]=(m[n][c])?1:0;
 	 
	}
	printf("\n");
}
int min(int x,int y)
{ 
  if(x<=y) return x;
  else return y;
}
int max(int x,int y)
{
  
  if(x>=y) return x;
  else return y;
}