装载问题回溯算法

最优装载问题的回溯算法，用回溯法解决装载问题的c++算法。

#include    
using namespace std;  
  
typedef int* pINT;  
template  
class Loading{  
public:  
           friend Type MaxLoading（Type* wint num Type C1int* bestx ）;  
   friend void SolveLoading（int C2bool* xint* wint num）;  
 
    void Backtrack（int i）;  
  
    int num;/* 集装箱数目 */  
    int * x;/* 当前解 */  
    int * bestx;/* 当前最优解 */  
      Type* w;/* 集装箱重量数组 */  
    Type  C1;/* 第一艘船的容量 */  
    Type cw;  
    Type bestw;  
   Type r;/* 剩余集装箱重量 */  
};  
 
template  
void Loading::Backtrack（ int i ）  
{  
   if（ i > num）{  
        if （ cw > bestw ） {  
           for （int i = 1; i <= num ; i++ ） {  
                bestx[i] = x[i];  
                bestw = cw;               
            }  
        }  
        return ;  
   }  
   r -= w[i];  
   if （ cw+w[i] <= C1 ） {  
       x[i] = 1;  
       cw += w[i];  
       Backtrack（i+1）;  
       cw -= w[i];  
    }  
 
    if （ cw+r > bestw ） {  
       x[i] = 0;  
        Backtrack（i+1）;  
    }  
  
    r += w[i];  
  
}  
template  
Type   MaxLoading（ Type* wint num Type C1int* bestx ）  
{  
   Loading X;  
   X.x = new int[num+1];  
    X.w = w;  
    X.C1= C1;  
    X.num = num;  
    X.bestx = bestx;  
    X.bestw = 0;  
    X.cw = 0;  
    X.r = 0;  
    for （int i = 1; i <= num ; i++ ） {  
       X.r += w[i];  
    }  
   X.Backtrack（1）;  
    delete[] X.x;  
    return X.bestw;  
  
}  
template  
 void    SolveLoading（ int C2int* xType* wint num ）  
 {  
     int totalW = 0;  
     int c1W = 0;/* 第一艘船总载重 */  
     for （int i = 1; i <= num ; i++ ） {  
         if （ x[i] == 1 ） {  
             c1W += w[i];  
         }   
         totalW += w[i];  
     }  
     if （ totalW-c1W > C2 ） {  
         printf（“没有合理的装载方案! :（ “）;  
         return;  
     }  
  
     printf（“ 装载方案如下:\n “）;  
     printf（“ 第一艘船装 “）;  
    for （int i = 1; i <= num ; i++ ） {  
        if （ x[i] == 1 ） {  
             printf（“%d “i）;  
         }   
     }  
     printf（“\n总载重 %d \n“c1W）;  
  
  
     printf（“ 第二艘船装 “）;  
     for （int i = 1; i <= num ; i++ ） {  
         if （ ! x[i] ） {  
             printf（“%d “i）;  
                      }   
                           }  
     printf（“\n总载重 %d \n“totalW-c1W）;  
  
}  
  
int main（int argcchar* argv[]）{  
  
    int C1 = 0;  
    int C2 = 0;  
    int num = 0;  
    int* x = NULL;  
    int** m = NULL;  
    int* w = NULL;  
  
    printf（“输入第一艘船最大载重量:“）;  
    scanf（“%d“&C1）;  
  
    printf（“输入第二艘船最大载重量:“）;  
    scanf（“%d“&C2）;  
  
  
    printf（“输入货物个数“）;  
    scanf（“%d“&num）;  
  
    x = new int[num+1];  
    w = new int[num+1];  
    m = new pINT[num+1];  
    for （int i = 0; i < num+1 ; i++ ） {  
        m[i] = new int[num+1];  
    }  
  
  
    printf（“分别输入货物重量（回车结束）：\n“）;  
  
    for （int i = 1; i <= num ; i++ ） {  
   

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      34972  2012-05-22 17:33  装载问题回溯算法\装载问题回溯算法.docx

     文件       3348  2012-05-22 17:23  装载问题回溯算法\zzhs.cpp

     文件     477406  2012-05-22 17:31  装载问题回溯算法\zzhs.exe

     目录          0  2012-05-22 17:34  装载问题回溯算法

----------- ---------  ---------- -----  ----

               515726                    4