pack.cpp

一个简化的背包问题：一个背包能装总重量为 T

#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; 
}