装载问题跌代回溯.cpp

回溯法实现多个经典算法

//? 装载问题跌代回溯

#include <iostream.h>
const int n=5;

void main()
{
	int C=65, W[n]={10,22,40,15,31};
	int j=0;  //已装上轮船的集装箱数
	int x[n]={0};  //装上轮船的集装箱号
	int m[n]={0};

	cout<<"\n轮船承载量："<<C;
	cout<<"\n\n集装箱重量：";
	for (int i=0; i<n; ++i) cout<<W[i]<<"  ";

	int n0=n;
	int min1=C;  //最小剩余量
	while (n0>0)
	{
		while (i>0)
		{
			if (C>=W[i-1])
			{
				x[j++]=i;
				C-=W[i-1];
			}
			i--;
		}

		if (j==n && C>0)
		{
			cout<<"\n\n所有集装箱都装上了轮船。";
			break;
		}

		if (C<min1)
		{
			min1=C;
			for (int k=0; k<j; ++k) m[k]=W[x[k]-1];
			for (k=j; k<n; ++k) m[k]=0;
		}

		if (C==0)
		{
			cout<<"\n\n装载解向量：";
			i=n;
			while (x[--i]==0) ;
			for (int k=1; k<=n; k++)
				if (k==x[i])
				{
					cout<<" 1  ";
					i--;
				}
				else cout<<" 0  ";
			cout<<"\n\n恰好装满轮船：";
			for (i=j-1; i>=0; --i) cout<<W[x[i]-1]<<"  ";
			break;
		}

		j--;
		i=x[j];
		C+=W[i-1];
		if (i==n0)
		{
			i=n0-1;
			n0=i;
		}
		else i--;
	}

	if (j==0)
	{
		cout<<"\n\n最优装载方案：";
		i=n;
		while (m[--i]==0);
		while (i>=0)
		{
			cout<<m[i]<<"  ";
			j+=m[i];
			i--;
		}
		cout<<"\n\n已经装载重量："<<j;
	}
	cout<<"\n\n";
}