两只船的装载问题 回溯法

描述： 有两艘船，载重量分别是c1、 c2，n个集装箱，重量是wi (i=1…n)，且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。 输入： 多个测例，每个测例的输入占两行。第一行一次是c1、c2和n（n<=10）；第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。 输出： 对于每个测例在单独的一行内输出Yes或No。 输入样例： 7 8 2 8 7 7 9 2 8 8 0 0 0 输出样例： Yes No 提示： 求出不超过c1的最大值max，若总重量－max < c2则能装入到两艘船。

//用回溯法，不带剪枝、限界函数

#include
#include

#define NUM	8

void maxloading（int const *wint constint）;
int n;				//记录集装箱的数量
int cw=0;			//当前载重量
int bestc=0;		//记录集装箱1的最大装载量

void main（）
{
	int c1c2;		//记录两只船的载重量	
	int i;
	int sum=0;		//存储每组数据的集装箱的总重量
	int counter=0;		//记录一组数据处理后的结果的下标
	bool tag[NUM];		//记录各组数据处理后的结果
	
//	printf（“Input c1 c2 and n:\n“）;
	scanf（“%d %d %d“&c1&c2&n）;

	int *w=（int *）malloc（sizeof（int）*n）;		//记录每个集装箱的重量

	for（i=0;i		tag[i]=false;

	while（n）
	{
		//printf（“Input weight of boxs:\n“）;
		for（i=0;i		{
			scanf（“%d“&w[i]）;
			sum=sum+w[i];
		}

		maxloading（wc10）;

		if（（sum-bestc）<=c2）
			tag[counter++]=true;