//? 裝載問題跌代回溯

#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";
}