当前位置 博文首页 > 爱新觉罗?炒饭的博客:装载问题(子集树回溯法)
题目最终要求的是选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近第一艘轮船的载重量。所以是子集树
约束函数:解向量的集装箱重量之和小于第一艘轮船载重量
限界函数:当前载重量cw+剩余集装箱的重量rest≤当前最优载重量bestw
考虑了限界函数的程序代码如下:
#include <iostream>
using namespace std;
int C=0; //第一艘轮船的载重量
int n=0; //集装箱数量
int x[100]; //当前解向量
int bestx[100]; //最优解向量
int w[100]; //集装箱重量数组
int cw=0; //当前载重量
int bestw=0; //最优载重量
int rest=0; //剩余集装箱重量和
void Backtrack(int t)
{
if(t>n)
{
if(cw>bestw)
{
bestw = cw;
for (int i = 1; i <= n;i++)
bestx[i] = x[i];
}
}
else
{
rest -= w[t];
if(cw+w[t]<=C) //满足约束函数搜索左子树
{
x[t] = 1;
cw += w[t];
Backtrack(t + 1);
cw -= w[t];
}
if(cw+rest>bestw) //当满足限界函数搜索右子树
{
x[t] = 0;
Backtrack(t + 1);
}
rest += w[t];
}
}
int main()
{
cout << "请输入集装箱的数量和第一艘轮船的载重量" << endl;
cin >> n >> C;
cout << "请输入每个集装箱的重量" << endl;
for (int i = 1; i <= n;i++)
{
cin >> w[i];
rest += w[i];
}
Backtrack(1);
cout << "最优值为:" << bestw << endl;
cout << "最优解为:";
for (int i= 1; i <= n;i++)
cout << bestx[i] << " ";
return 0;
}
cs