#include <iostream> 
using namespace std; 

int Knap(float,int); 

float weight[100]; 
int flag[100]={0}; 
int fl=0;int nn; //全局變量，保存物品總數
int Knap(float sum,int n) //在主函數中nn-1把值傳遞給n，從而保證全局變量nn不被修改，但程序中卻能用n去遞歸
{ 
     int i; 

     if (sum==0) { 
       for(i=0;i<nn;i++) 
        if(flag[i]) 
        cout<<"choose"<<weight[i]<<endl;		cout<<endl; 
        
        fl=1; 
        return 1; //程序跳出		} 
    else if (sum<0||(sum>0&&n<0)) 
     return 0; 

      flag[n]=1; 
      i=Knap(sum-weight[n],n-1); 
      flag[n]=0; 
      i=Knap(sum,n-1); 

    if(fl) 
    return 1; 

      return 0; 
}
int main() 
{ 
     float sum; 

     cout<<"How much total weight:"<<endl; 
     cin>>sum; 
     cout<<"How many units goods:"<<endl; 
     cin>>nn; 

     cout<<"Input weight:"<<endl; 
     for (int i=0; i<nn; i++) 
        cin>>weight[i]; 
     if (Knap(sum,nn-1)==0) 
     cout<<"No solution"<<endl; 

     system("pause"); 
     return 0; 
}