最优装载问题

用回溯法设计求解装载问题的算法,并分析时间复杂度。

装载问题:有一批共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"没有合适方案";
 }

 

上一篇:五种I/O模式


下一篇:关于epoll的详解说明关于epoll的详解说明