main.cpp

输入物品的个数和背包的负重大小；程序自动为每个物品的重量和价值赋一个随机值(范围10~80)

/////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <functional>



#define		DATAMAXSIZE			(1024)
#define		QUEUEMAXSIZE		(80000000)
#define		INTERVAL			(-1)


typedef struct	_PACKET
{
	unsigned int			weight;
	unsigned int			value;
	int						in;//in = 0 该包未放入， = 1 该包已经放入
}PACKET, *PPACKET;


typedef struct  _QUEUE
{
	int			wt;  //=current total weight
	int			wp; // =current total  value 

	int			level;
}QUEUE, *PQUEUE;

PACKET			packet[DATAMAXSIZE];
int				cw;						//当前重量 current weight
int				n;						//共n个物品
int				c;						//背包总重量   
int				cp;						//当前价值 current price
int				tp;						//总价值   total price 
int				tw;						//总重量   total weight
int				x[DATAMAXSIZE];				//X[i] = 0 不选中I包， = 1 选中该包


int				bestp;//当前最佳价值     best price 

QUEUE			queue[QUEUEMAXSIZE];
int				rear, front;

class	compare
{//比较器 
public:
	bool operator()(const QUEUE& a, const QUEUE& b){return a.wp < b.wp;}
};

std::priority_queue<QUEUE, std::vector<QUEUE>, compare>		q;//价值 优先队列

void	initqueue()
{
	rear = -1;
	front = -1;
}
void	enqueue(int i, int wt, int wp)
{//
	if(wp > bestp)
	{
		bestp = wp;//current best value ( price )
	}
	front++;
	queue[front].wt = wt;
	queue[front].wp = wp;
}

void dequeue(int* wt, int* wp)
{
	rear++;
	
	*wt = queue[rear].wt;
	*wp = queue[rear].wp;
	return;
}



int	GetRandom()
{
	return rand()%70 + 10;//物品的重量和价值范围10~80
}

int	birth_Packet(int len)
{
	printf("\n物品的重量和价值范围为：10 ~ 80 \n\n");
	int		i;
	for(i = 0; i < len; i++)
	{
		packet[i].weight = GetRandom();
		packet[i].value = GetRandom();
		packet[i].in = 0;
		printf("packet[%d].weight = %d  value = %d \n",i,packet[i].weight,	packet[i].value);
	}
	return 0;
}

void backTrack_Init(int	k)
{
	int		i;
	n = k;
	cw = cp = tp = tw = 0;
	for(i = 0; i < k;i++)
		x[i] = 0;
//全部未选中
//	c = PACKETSIZE;
	

	for(i = 0; i < k; i++)
		packet[i].in = 0;
}

void	fifo_init(int k)
{
	int		i;
	n = k;
//	c = PACKETSIZE;	
//	printf("输入背包负重大小：\n");
//	scanf("%d",&c);
	for(i = 0; i < k;i++)
	{
		packet[i].in = 0;
		x[i] = 0;
	}
}


int	backTrack_Knap(int i)
{
	if(i >= n)
	{
		int		k;
		if(tp < cp)
		{
			tp = cp;
			tw = cw;
			for(k = 0; k < n; k++)
				x[k] = packet[k].in;
		}
		//找到一个可行解
		//通过回溯修改成最佳解
		return 0;
	}
	
	//是否能放入第i个物品
	if(cw + packet[i].weight <= c)
	{
		packet[i].in = 1;//放入
		cw += packet[i].weight;
		cp += packet[i].value;
		backTrack_Knap(i + 1);
		cp -= packet[i].value;
		cw -= packet[i].weight;
		packet[i].in = 0;
	}
	
	//不放入第i个物品的情况
	backTrack_Knap(i + 1);
}

int	fifo_Knap(int k)
{
	int	i = 0 , ew = 0 , ep = 0;//当前重量  当前价值 
	int		tmp = 0;
	int	r = 0;

	fifo_init(k);
	initqueue();
	enqueue(0, INTERVAL, 0);

	for(i = 1; i < n; i++)
		r += packet[i].value;// r = total value

	i = 0;
	ep = ew = bestp = 0;
	while(1)
	{
		if(i < n)
		{
			if(ew + packet[i].weight <= c)//可行则拿入包
				enqueue(i, ew + packet[i].weight, ep + packet[i].value);//自己的队列
			
			if(ep + r > bestp)// 相当于限界函数 当前价值 加上 剩余全部价值 〉bestp --> enqueue
				enqueue(i, ew, ep);
		}

		dequeue(&ew, &ep);//修改ew ,ep,通过了上面的限界函数函数的检测，才能留在队列中
		
		if(ew == INTERVAL)
		{//选择一个最有利的节点作为扩展节点（剪枝）。
			if(rear == front)
				return bestp;
			enqueue(0, INTERVAL, 0);
			dequeue(&ew, &ep);//修改ew ,ep
			i++;
			r -= packet[i].value;
		}
	}
}

void		lc_init(int k)
{
	int		i;
	n = k;
//	c = PACKETSIZE;	
	
	for(i = 0; i < k;i++)
	{
		packet[i].in = 0;
		x[i] = 0;
	}
}

int	lc_Knap(int k)
{
	int	i, ew, ep = 0;//当前重量  当前剩余价值 
	int		tmp;

	QUEUE	qtmp;

	lc_init(k);

	for(i = 0; i < n; i++)
		ep += packet[i].value;//全部价值

	i = 0;
	ew = bestp = 0;
	
	while(i < n)
	{
		if(i < n)
		{
			if(ew + packet[i].weight <= c)
			{//可行则拿入包
				qtmp.wp = ep;
				qtmp.wt = ew + packet[i].weight;
				qtmp.level = i + 1;

				q.push(qtmp);//入  " 价值 "  优先队列
			}
			
			if(ep > bestp)
			{// 相当于限界函数 当前剩余价值  〉bestp --> enqueue
				qtmp.wp = ep - packet[i].value;
				qtmp.wt = ew;
				qtmp.level = i + 1;
				q.push(qtmp);
			}
		}

		qtmp = q.top();
		q.pop();

		ep = qtmp.wp;
		ew = qtmp.wt;
		i = qtmp.level;

	}
	
	if(bestp < ep)
		bestp = ep;

	return bestp;
}


void main()
{
	int	i;

	srand((unsigned int)time(NULL));
	
	//////////////////////////////////////////////////////////////////test
	
	
	int packszk ;
	//getchar();
	do
	{
		printf("输入物品个数：\n");
		scanf("%d",&packszk);
		if(packszk <= 0 )printf("物品个数要大于0!\n");
		if(packszk >   DATAMAXSIZE) printf("物品个数大于上限!\n");
	}while(packszk <= 0 || packszk > DATAMAXSIZE);
	do{
		printf("输入背包负重大小：\n");
		scanf("%d",&c);
	}while(c <= 0);

	birth_Packet(packszk);
	backTrack_Init(packszk);
	backTrack_Knap(0);

/*	for(i = 0; i < packszk; i++)
	{	//测试是否有空的背包
		if(i && !(i%5))
			putchar('\n');
		printf("%d  ", x[i]);
	}*/

	printf("\n回溯法:\ntotal weight:%d\n", tw);
	printf("total value:%d\n", tp);



	tp = fifo_Knap(packszk);
	printf("\nFIFO分支限界法:\ntotal weight:%d\n", tw);
	printf("total value:%d\n", tp);




	tp = lc_Knap(packszk);
	printf("\nLC分支限界法:\ntotal weight:%d\n", tw);
	printf("total value:%d\n", tp);
}