minweight.c

计算机算法上最小重量机的回溯法和分支限界法的实现

#include<stdio.h>
#include<stdlib.h>

#define		N		3
#define		M		3
#define		TRUE	1
#define		FALSE	0

typedef struct tag_MinWeight_t
{
	//费用及重量矩阵
	int p[N+1][M+1];
	int w[N+1][M+1];

	//总价格上界
	int cost;

	//当前部件采购方案
	int x[N+1];

	//最优方案
	int bestx[N+1];

	//当前价格
	int cp;

	//当前重量
	int cw;

	//最小重量
	int bestw;


}MinWeight_t;

MinWeight_t X;


void Backtrack(int t)
{
	int i;
	if(t > N)
	{
		if(X.cw < X.bestw)
		{
			for(i = 1; i <= N; i++)
				X.bestx[i] = X.x[i];
			X.bestw = X.cw;
		}
	}
	else
	{
		for(i = 1; i <= M; i++)
		{
			X.x[t] = i;
			X.cp = X.cp + X.p[t][X.x[t]];
			X.cw = X.cw + X.w[t][X.x[t]];

			if((X.cp <= X.cost) && (X.cw < X.bestw))
				Backtrack(t+1); 
			X.cp = X.cp - X.p[t][X.x[t]];
			X.cw = X.cw - X.w[t][X.x[t]];
		}
	}
}

int main()
{
	int i, j;
	X.cost = 4;
	X.cp = 0;
	X.cw = 0;
	X.bestw = 32767;

	printf("请输入价格矩阵：\n");
	for(i = 1; i <= N; i++)
		for(j = 1; j <= M; j++)
			scanf("%d", &(X.p[i][j]));

	printf("请输入重量矩阵：\n");
	for(i = 1; i <= N; i++)
		for(j = 1; j <= M; j++)
			scanf("%d", &(X.w[i][j]));

	Backtrack(1);

	printf("最优解是：");

	for(i = 1; i <= N; i++)
		printf("%d ", X.bestx[i]);
	printf("\n最优值：%d\n", X.bestw);

	return 0;
}