bag.cpp

本程序是用c++实现的背包问题。相信会对大家有用的

//***********************************
//背包问题（贪心法）                *
//编程时间：2007.11.29              *
//编程者：王向红                    *
//***********************************
#include<iostream.h>
#define N 8
void main()
{
	int i,j,t,m,sum=0,Ti[N]={40,55,20,65,30,40,45,35},
		Jia[N]={35,20,20,40,35,15,40,20};
	float TIJIA[N],k;	
	char n,DAI[N]={'A','B','C','D','E','F','G','H'};
	for(i=0;i<N-1;i++)
		TIJIA[i]=(float)Jia[i]/Ti[i];
	for(i=0;i<N-1;i++)
		for(j=i+1;j<N;j++)
		 //	 if(Jia[i]<Jia[j])     //每次取价值最大值
	  	 // if(Ti[i]>Ti[j])       // 每次取体积最小值
		   if(TIJIA[i]<TIJIA[j]) //每次取单位体积最大值
			{
				t=Jia[i],   Jia[i]=Jia[j],     Jia[j]=t;      
				m=Ti[i],    Ti[i]=Ti[j],       Ti[j]=m;
				k=TIJIA[i], TIJIA[i]=TIJIA[j], TIJIA[j]=k;
				n=DAI[i],   DAI[i]=DAI[j],     DAI[j]=n;
			}
			for(i=0;sum<=200;i++)
			{
			 sum+=Ti[i];
			 if(sum<=200)
			 cout<<DAI[i]<<"\t";
			 else if((sum-200)<Ti[i])
		     cout<<" 其中剩余体积为"<<Ti[i]-sum+200<<"的部分从 "<<DAI[i]<<" 中装入"<<"\n";
			}
	
}