装载问题 - 分支限界算法

本贴最后更新于 2251 天前,其中的信息可能已经时移世异

装载问题

集装箱装载问题要求在不超过轮船载重量的前提下,将尽可能多的集装箱装上船;

样例:

   输入:



   80 4



   18 7 25 36



   输出:



   79

分析:

本题可采用 FIFO 队列式分支限界算法,将解空间树的所有节点按照广度搜索的顺序排列成一个先进先出的队列,并用-1 作为每一层的分割符。

C++ 实现:


    #include "iostream"

    #include "queue"

    #define NUM 100

    using namespace std;



    int n;

    int c;

    int w[NUM];



    int MaxLoad()

    {

        queue<int> Q;

        Q.push(-1);

        int i=0;

        int Ew=0;

        int bestw=0;

        int r=0;

        for(int j=1;j<n;j++)

        {

            r+=w[j];

        }

        while(1)

        {

            int wt=Ew+w[i];

            if(wt<=c)

            {

                if(wt>bestw)

                    bestw=wt;

                if(i<n-1)

                    Q.push(wt);

            }

            if(Ew+r>bestw&&i<n-1)

                Q.push(Ew);

            Ew=Q.front();

            Q.pop();

            if(Ew==-1)

            {

                if(Q.empty())

                    return bestw;

                Q.push(-1);

                Ew=Q.front();

                Q.pop();

                i++;

                r-=w[i];

            }

        }

        return bestw;

    }



    int _tmain(int argc, _TCHAR* argv[])

    {

        int x;

        cout<<"请输入轮船载重量和集装箱个数:";

        cin>>c>>n;

        cout<<"每个集装箱的重量为:";

        for(int i=0;i<n;i++)

        {

            cin>>x;

            w[i]=x;

        }

        cout<<"最大装载量为:"<<MaxLoad()<<endl;



        return 0;

    }

  • 设计
    111 引用 • 796 回帖 • 1 关注
  • 学习

    “梦想从学习开始,事业从实践起步” —— 习近平

    160 引用 • 470 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...