#include<iostream.h>

#include<stdlib.h>

 
int  knap (int s, int n, int w[])
{
	if (s == 0)
	{ return 1;}

	else if (s < 0 )
	{ return 0;}
	
	else if ( s > 0 && n < 1)
	{return 0;}
	
	else if (knap (s - w[n - 1], n - 1, w) == 1)
	{
		cout<<"包中有：第"<<n<<"個(gè)物品，質(zhì)量為"<<w[n-1]<<endl;
		return (1);
	}
	else
		return (knap (s, n - 1, w));
}
 
 
void main ()
{
	int *w;
	int s = 0, n = 0, result = 0, i = 0;
	 cout<<"包中最多可裝載的重量為：";	/*輸入s */
	  cin>>s;
    if(s==0)
	{cout<<"此背包問題一定有解"<<endl;
	  exit(0);
	}
	 if (s < 0 )
	 {
		 cout<<"總質(zhì)量不能為負(fù)數(shù)"<<endl;
	   exit(0);
	 }
	
	  cout<<"請(qǐng)輸入n值： ";	/*輸入n */
	  cin>>n; 
	  if ( s > 0 && n < 1)
	  {
		  cout<<"物品件數(shù)不能為負(fù)數(shù)"<<endl;
	    exit(0);
	  }
	w = new int[n];
	  cout<<"請(qǐng)輸入這"<<n<<"個(gè)物品的質(zhì)量:"<<endl;	/*輸入重量 */
	for (i = 0; i < n; i++)
		cin>>w[i];
	result = knap (s, n, w);
	if (result == 0)
	  cout<<"此背包為題無解"<<endl;
	 
}