0-1背包问题.cpp

王晓东算法设计与分析课后一些题目的源码。vc下全都编译通过。且在学校网站上提交通过。是学习算法较好的参考资料

#include<iostream>  
using namespace std;   
class Knapsack{  
public:  
	Knapsack(double *pp,double *ww,int nn,double cc){  
	p = pp;  
    w = ww;  
    n = nn;  
    c = cc;  
    cw = 0;  
    cp = 0;  
    bestp = 0;  
    x = new int[n];  
    cx = new int[n];  
   }  
   void knapsack(){  
       backtrack(0);  
    }  
   
    void backtrack(int i){
        if(i > n){  
           if(cp > bestp){  
               bestp = cp;  
               for(int i = 0; i < n; i++)  
              x[i] = cx[i];  
            }  
            return;  
        }  
    
         if(cw + w[i] <= c){
            cw += w[i];  
            cp += p[i];  
            cx[i] = 1;  
			backtrack(i+1);  
			cw -= w[i];  
			cp -= p[i];  
        }  
        cx[i] = 0;  
        backtrack(i+1);
    }  
    void printResult(){  
		cout << "Optimal value is" << endl << bestp << endl;    
        for(int i = 0; i < n; i++){  
			if(x[i] == 1)  
			    cout << 1 << " ";  
			else
					cout << 0 << " ";
			}  
			cout << endl;  
       }  
   
 private:  
		double *p,*w;  
		int n;  
		double c;  
		double bestp,cp,cw; 
		int *x,*cx;  
};  
int main()
{
	int n;
	double c;
	cin >> n;
	cin >> c;
	double *p = new double[n];
	double *w = new double[n];
	for(int i=0;i<n;i++)
		cin >> p[i];
	for(int j=0;j<n;j++)
		cin >> w[j];
	Knapsack ks = Knapsack(p,w,n,c);
	ks.knapsack();
	ks.printResult();
	return 0;
}