回溯算法3——装箱问题

有n个集装箱要装到两艘船上，每艘船的容载量分别为cl, c2,第i个集装箱的重量为w[i]， 同时满足: w[]+w[2)+.+w[n]<=c1+c2; 确定一个最佳的方案把这些集装箱装入这两艘船上。
【分析】
最佳方案的方法:首先将第一艘船尽量装满，再把剩下的装在第二艘船上。第一艘船尽量装满，等价于从n个集装箱选取一一个子集，使得该子集的问题解空间: (x1, x2, x3， . xn)，其中，xi为0表示不装在第一艘船上，为1表示在第一艘船上;
约束条件:
(1)可行性约束条件: w1xx1+w2x2...ixi.+..+wn * xn<=c1。
(2)最优解约束条件: remain+cw>bestw (remain 表示剩余集装箱重量，cw表示当前已装上的集装箱的重量，bestw 表示当前的最优装载量)。
例如，集装箱的个数为4，重量分别是10、20、35、40,第一艘船的最大装载量是50，则最优装载是将重量为10和40的集装箱装入。首先从第一个集装箱开始，将重量为10的集装箱装入第一艘船， 然后将重量为20的集装箱装入，此时有10+20< -50，然后试探将重量为35的集装箱装入，但是10+20+35>50，所以不能装入35，紧接着试探装入重量为40的集装箱，因为10+20+40>50，所以也不能装入。因此30成为当前的最优装载量。取出重量为20的集装箱(回溯，重新调整问题的解)，如果将重量为35的集装箱装入第一艘船，因为10+35<50， 所以能够装入。因为45>bestw，所以45作为当前最优装载量。

继续取出重量为35的集装箱，如果将重量为40的集装箱装入第一艘船，因为10+40≤50，所以装入第一艘船。 因为50>bestw,所以50作为当前最优装载量。

code：

#include<stdio.h>
#include<malloc.h>
#include <iostream>
int *w;		/*存放每个集装箱的重量*/
int n;		/*集装箱的数目*/
int c;		/*第一艘船的承载量*/
int cw = 0;	/*当前载重量*/
int remain;	/*剩余载重量*/
int	*x;		/*存放搜索时每个集装箱是否选取*/
int bestw;	/*存放最优的放在第一艘船的重量*/
int	*bestx;	/*存放最优的集装箱选取方案*/
void Backtrace(int k)
{
	int i;
	if (k > n)	 /*递归的出口，如果找到一个解*/
	{
		for (i = 1; i <= n; i++)	/*则将装入的方法存入bestx中*/
			bestx[i] = x[i];
		bestw = cw;			/*记下当前的最优装载量*/
		return;
	}
	else
	{
		remain -= w[k];
		if (cw + w[k] <= c) /*如果装入w[k]，还小于c*/
		{
			x[k] = 1;		/*则装入w[k]*/
			cw += w[k];
			Backtrace(k + 1);
			cw -= w[k];	/*不装入w[k]*/
		}
		if (remain + cw > bestw)	/*如果剩余的集装箱不能完全装入*/
		{
			x[k] = 0;
			Backtrace(k + 1);		/*继续从剩余的集装箱中检查是否能装入*/
		}
		remain += w[k];		/*w[k]重新成为待装入的集装箱*/
	}
}
int BestSoution(int *w, int n, int c)
/*搜索最优的装载方案:w存放每个集装箱的重量,
n表示集装箱数目,c表示第一艘船的装载量*/
{
	int i;
	remain = 0;/*第一艘船剩下的装载量*/
	for (i = 1; i <= n; i++)
	{
		remain += w[i];
	}
	bestw = 0;/*初始化第一艘船最优装载量*/
	Backtrace(1);
	return bestw;
}
void main()
{
	int i;
	printf("请输入集装箱的数目=");
	scanf("%d", &n);
	w = (int*)malloc(sizeof(int)*(n + 1));
	x = (int*)malloc(sizeof(int)*(n + 1));
	bestx = (int*)malloc(sizeof(int)*(n + 1));
	printf("请输入第一艘船的装载量=");
	scanf("%d", &c);
	printf("请输入每个集装箱的重量:\n");
	for (i = 1; i <= n; i++)
	{
		printf("第%d的重量=", i);
		scanf("%d", &w[i]);
	}
	bestw = BestSoution(w, n, c);
	for (i = 1; i <= n; i++)
	{
		printf("%4d", bestx[i]);
	}
	printf("\n");
	printf("存放在第一艘船上的重量:%d\n", bestw);
	free(w);
	free(x);
	free(bestx);
	system("pause");
}

结果：