装载问题
集装箱装载问题要求在不超过轮船载重量的前提下,将尽可能多的集装箱装上船;
样例:
输入:
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;
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于