装载问题
参考：计算机算法设计与分析（第三版）王晓东 编著
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.zzzyk.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");
}
补充：软件开发 , C++ ,
