header.h

一个简单的01背包算法

#include <stdio.h>

void InitializePW(int number);
void FindXValue(int time,int weightofbag);
void sort(int i,int iw,int ip);
//void error1();
int P[100],W[100],F[10],X[10];

int Weight[10];
int Profit[10];

void InitializePW(int number)
{
	int time,tp,tw,end,i,k;
	//int f[10];
//	printf("access initializePW\n");
	P[0]=0;
	W[0]=0;
	int j=1;
	F[0]=0;

	//time从1开始到物品的数量number结束循环
	for(time=1;time<=number;time++)
	{
		end=0;
		F[time]=j;
		//tp和tw记录本次用来比较的效益和重量值，以确定覆盖开始
		tp=Profit[time]+P[F[time-1]];
		tw=Weight[time]+W[F[time-1]];
		//本次循环比较开始，依次取上一段的P、W值比较
		for(i=F[time-1];i<F[time]&&!end;i++)
		{
			//i为从上一段中取出的pw对的序号，先复制到本段的相应位置j
			P[j]=P[i];
			W[j]=W[i];
			//先检查刚赋完的pw值是否满足支配规律而需要用tp、tw替换
			if(tw<=W[i]&&tp>=P[i])
			{
				//若本段刚赋完的值满足支配规律，则将其用tp、tw覆盖
				P[j]=tp;
				W[j]=tw;
				//再取得上一段的第二个位置，循环直到上一段取完
				k=F[time-1]+1;
				while(k<F[time])
				{
					j++;
					P[j]=P[k]+Profit[time];
					W[j]=W[k]+Weight[time];
					k++;
				}
				end=1;
				//设置结束标记，表明本段已经处理完毕
			}
			//再检查上一段的序号标记i是否到达本段的起始位置，若已经取完，则从下一个j开始将本段赋值
			if(i==F[time]-1&&!end)
			{
				k=F[time-1];
				//k取得上一断的起始位置，循环直到k到达本段的开头位置
				while(k<F[time])
				{
					j++;
					P[j]=P[k]+Profit[time];
					W[j]=W[k]+Weight[time];
					k++;
				}
				end=1;
				//设置结束标记，表明本段已经处理完毕
			}

            //若不满足支配规律且前一段的值还没取完，则j+1是必须的。进入下一轮循环继续拷贝。
			//若本段处理已经结束，则j+1后便为下一次要处理的段的起始位置
			j++;
		}
	}
	F[number+1]=j;

//	for(i=0;i<=21;i++)
//	{
//	printf("%d,%d\n",P[i],W[i]);
//	}
	//return f;
}

/////////////////
void FindXValue(int time,int weightofbag)
{
	int tempw,end=0;
    int t,i;
	tempw=weightofbag;
	for(t=time;t>0;t--)
	{
		end=0;
//		printf("FX1");
		for(i=F[t];i<F[t+1]&&!end;i++)
		{
//			printf("FX2");
			if(W[i]==tempw)
			{
//				printf("FX3");
				if(F[t]-F[t-1]>=i-F[t]+1)
				{
//					printf("FX4");
					if(W[F[t-1]+i-F[t]]==W[i]&&P[F[t-1]+i-F[t]]==P[i])
						X[t]=0;
					else
						X[t]=1;
				}
				else 
					X[t]=1;
				end=1;
			}
//			else 
//				printf("error\n");
		}
		if(X[t]==1)
			tempw=W[i-1]-Weight[t];
//		else
//			tempw=W[i-1];
	}
}

///////////////////
void sort(int i,int iw,int ip)
{
	int k,j;
	for(k=0;Weight[k]<=iw&&k<i;k++);
	if(i==k)
	{
		Weight[k]=iw;
		Profit[k]=ip;
	}
	else
	{
	for(j=i-1;j>k;j--)
	{
		Weight[j+1]=Weight[j];
		Profit[j+1]=Profit[j];
	}
    Weight[j+1]=Weight[j];
	Profit[j+1]=Profit[j];
	Weight[j]=iw;
	Profit[j]=ip;
	}
}

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