欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯算法3——装箱问题

程序员文章站 2022-06-04 10:50:29
...

有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");
}

结果:

回溯算法3——装箱问题