装载问题

#include<stdio.h>
#include <stdlib.h>
int MaxLoading(int w[],int c,int n,int bestx[])//迭代回溯法,返回最优载重量及其相应解,初始化根结点  
{  
    int i=1,j;//当前层,x[1:i-1]为当前路径  
    int *x=new int[n+1];  
  
     int bestw=0;      //当前最优载重量  
     int  cw=0;         //当前载重量  
    int  r=0;          //剩余集装箱重量  
  
    for ( j=1;j<=n;j++)  
    {  
        r+=w[j];  
    }  
  
    while(true)//搜索子树  
    {       
        while(i<=n &&cw+w[i]<=c)//进入左子树  
        {  
            r-=w[i];  
            cw+=w[i];  
            x[i]=1;  
            i++;  
        }  
          
        if (i>n)//到达叶结点  
        {        
            for (int j=1;j<=n;j++)  
            {  
                bestx[j]=x[j];  
            }  
            bestw=cw;  
        }  
        else//进入右子树  
        {            
            r-=w[i];  
            x[i]=0; i++;  
        }  
        while (cw+r<=bestw)  
        { //剪枝回溯  
            i--;     
            while (i>0 && !x[i])  
            {   
                r+=w[i];  
                i--;  
            }     
            //从右子树返回  
            if (i==0)  
            {  
                delete []x;  
                return bestw;  
            }  
            x[i]=0;  
            cw-=w[i];  
            i++;  
        }   
    }
}
int main()
{
    int n=3,m,m2,i,j;  
    int c=50,c2=50;  
    int w[4]={0,10,40,40};  
    int bestx[4];
    m=MaxLoading(w, c, n, bestx); 
    printf("轮船的载重量分别为:");  
    printf("c1=%d    c2=%d
",c,c2);
    printf("待装集装箱重量分别为:");  
    printf("w(i)=");  
    for (i=1;i<=n;i++)  
    {  
        printf("%d  ",w[i]);  
    }  
    printf("
");  
    printf("");
    printf("在第一艘船上的装载量为%d
",m);  
    printf("在第一艘船上放入的物品是:
");
    for ( i=1;i<=n;i++)  
    {  
        printf("%d  ",bestx[i]);  
    }  
    printf("
");  
                                                                                                                                                                                                                                                    
     m2=0;  
    for (j=1;j<=n;j++)  
    {  
        m2=m2+w[j]*(1-bestx[j]);  
    }  
    printf("第二艘船上的物品为m(2)=%d  
",m2);  
  
    if(m2>c2)   
    {  
        printf("因为m(2)大于c(2),所以原问题无解!
");  
    }   
    return 0;
}
原文地址:https://www.cnblogs.com/jweie/p/9285556.html