用回溯法设计求解装载问题的算法,并分析时间复杂度。
装载问题:有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且w1+w2+…+wn<=c1+c2。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有,找出一种装载方案。
此问题是一个可行解的问题
首先,确定有解无解;如果有解,给出解决方案
装载方案:
(1)将第一艘轮船尽可能装满(第一艘轮船优化问题)
(2)将剩余的集装箱装在第二艘轮船上
问题:n,c1,c2,{w[1],w[2],...,w[i],...w[n]}
解表示:就是决策过程,把每个集装箱选择还是不选择计算出一个值,有n个集装箱,共有n个决策
X[0..n]
tw,rw,i,maxW
tw:已装载到第一艘轮船上的集装箱重量之和
rw:剩余的集装箱重量和
i:表示考虑的集装箱i
maxW:当前装载方案中,最优方案中的最大装载的集装箱的重量总和
求解步骤:
1、将第一艘轮船尽可能装满,得到解向量x(简单装载问题的过程)
对于第i个集装箱扩展规则:如果tw+w[i]<=c1,就扩展左分支,x[i] = 1,tw = tw+w[i],rw = rw-w[i]
如果tw+rw-w[i]>maxW,就扩展右分支,x[i] = 1,rw = rw-w[i]
2、累计第一艘轮船装完后剩余的集装箱重量sum
3、若sum<=c2,表示第二搜轮船可以装完,返回true
否则表示第二艘轮船不能装完,返回false
/* tw:已装载到第一艘轮船上的集装箱重量之和 rw:剩余的集装箱重量和 i:表示考虑的集装箱i maxW:当前装载方案中,最优方案中的最大装载的集装箱的重量总和 //op表示一个解,即一个选择方案 //i表示考虑的集装箱i */ void dfs(int tw,int rw,int op[],int i) { if(i>n) //所有集装箱已被处理 { if(tw<=c1 && tw>maxW) { maxW = tw; for(int j = 1;j<=n;j++) //复制决策 x[j] = op[j]; } }else { op[i] = 1; //第i个集装箱被选择 if(tw + w[i]<=c1) //左剪枝 扩展结点 dfs(tw+w[i],rw-w[i],op,i+1); op[i] = 0; //不选择第i个集装箱 if(tw + rw -w[i]>maxW) dfs(tw,tw-w[i],op,i+1); } } bool solve() { int sum = 0; for(int j=1;j<=n;j++) if(x[j] == 0) sum +=w[j]; if(sum<=c2) return true; else return false; } void main() { int op[MAXN]; memset(op,0,sizeof(op)); int rw = 0; for(int i=1;i<=n;i++) rw+=w[i]; dfs(0,rw,op,1); cout<<"求解结果\n"; if(solve()) { cout<<"装载方案\n"; displaySolution(n); } else cout"没有合适方案"; }