minweight.cpp

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

#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

const int N = 3;
const int M = 3;
const int COST = 4;

struct MinHeapNode
{
	int s;	//已确定s个部件的方案
	int *x; //前s个部件的采购方案x[0:s-1]
	int bb; //当前结点重量估计下界 
	int cp; //当前结点处价格和
	int cw; //当前结点处总重量；

	MinHeapNode(int n)
	{
		x = new int[n];
		
		for(int i = 0; i < n; i++)
			x[i] = i;
		
		s = bb = cp = cw = 0;
	}

	MinHeapNode(MinHeapNode &E, int Ecp, int Ecw, int Ebb, int n)
	{
		x = new int[n];

		for(int i = 0; i < n; i++)
			x[i] = E.x[i];
		s = E.s + 1;
		bb = Ebb;
		cp = E.cp + Ecp;
		cw = E.cw + Ecw;
	}
	
};

struct cmp 
{
    bool operator() (const MinHeapNode &a, const MinHeapNode &b) 
	{
        return (a.bb > b.bb);
    }
};

class MinWeight
{
public:

	//费用及重量矩阵
	int p[N][M];
	int w[N][M];

	//总价格上界
	int cost;

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

	//最小重量
	int bestw;

	

	MinWeight(void);	
	void BBMachine(void);
	int Bound(MinHeapNode &E,int k);
};

MinWeight::MinWeight(void)
{
	int i,j;
	cost = COST;
	bestw = 32767;

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

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

	this->BBMachine();
}

int MinWeight::Bound(MinHeapNode &E, int k)
{
	int sum = w[E.s][k];
	int min = 0;
	for(int i = E.s+1; i < N; i++)
	{
		min = w[i][0];

		for(int j = 1; j < M; j++)
		{
			if(min > w[i][j])
				min = w[i][j];
		}
		sum = sum + min;
	}

	return (sum + E.cw);
}


void MinWeight::BBMachine(void)
{
	priority_queue<MinHeapNode, vector<MinHeapNode>, cmp> H;

	MinHeapNode E(N);

	while(true)
	{
		int i;
		if(E.s == N)
		{
			// 叶结点
			if(E.cw < bestw)
			{
				for(i = 0; i < N; i++)
					bestx[i] = E.x[i];
				bestw = E.cw;
			}

			break;
		}

		else
		{
			for(i = 0; i < M; i++)
			{
				E.x[E.s] = i;
				int bb = Bound(E,i);

				if((E.cp + p[E.s][i] <= cost) && (bb < bestw))
				{
					MinHeapNode Machine(E, p[E.s][i], w[E.s][i], bb, N);
					H.push(Machine);
				}

			}
		}

		delete []E.x;

		if(H.empty())
		{
			printf("\tMin Heap Empty \n");
			break;
		}
		else 
		{
			E = H.top();
			H.pop();
		}
	}

	while(!H.empty())
	{
		delete []H.top().x;
		H.pop();
	}
}



int main()
{
	int i;
	MinWeight M;

	printf("最优解是：");

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


	return 0;
}