參考：計算機算法設計與分析（第三版）王曉東 編著 1、只返回能裝載的最大值 [cpp] #include <iostream> #include <cstdlib> #include <time.h> #include <utility> #include <string> using namespace std; template<class T> class Loading{ public: Loading(T w[],int n,T c); void backTrack(int t); int getBest(){ backTrack(0); return bestw; } private: int n; T *w,c,cw,bestw; }; template<class T> Loading<T>::Loading(T w[],int n,T c){ this->w=w; this->n=n; this->c=c; cw=0; bestw=0; } template<class T> void Loading<T>::backTrack(int t){ if(t>=n){ if(cw>bestw) bestw=cw; return; } if(cw+w[t]<=c){ cw+=w[t]; backTrack(t+1); cw-=w[t]; } backTrack(t+1); } void main(){ int w[]={10,20,30,40,50,60}; int c=200; Loading<int> L(w,6,200); cout<<L.getBest()<<endl; cout<<endl; system("pause"); } 2、返回能裝載的最大值和最優解 [cpp] #include <iostream> #include <cstdlib> #include <time.h> #include <utility> #include <string> using namespace std; template<class T> class Loading{ public: Loading(T w[],T c,int n); void backTrack(int t); int getBest(){ backTrack(0); return bestw; } int* getBestX(){ return bestx; } private: int n; T *w,c,cw,bestw, r, *x, *bestx; }; template<class T> Loading<T>::Loading(T w[],T c,int n){ this->w=w; this->c=c; this->n=n; cw=0; bestw=0; r=0; for(int i=0;i<n;i++) r+=w[i]; x=new int[n]; bestx=new int[n]; } template<class T> void Loading<T>::backTrack(int t){ if(t>=n){ if(cw>bestw){ for(int i=0;i<n;i++) bestx[i]=x[i]; bestw=cw; } return; } r-=w[t]; if(cw+w[t]<=c){ x[t]=1; cw+=w[t]; backTrack(t+1); cw-=w[t]; } if(cw+r>bestw){ x[t]=0; backTrack(t+1); } r+=w[t]; } www.2cto.com void main(){ int w[]={10,40,40}; int c=60; Loading<int> L(w,c,3); cout<<L.getBest()<<endl; cout<<endl; system("pause"); }
