0-1背包回溯.cpp

0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯

#include <iostream>
#include <iomanip>
#include "class.h"

using namespace std;
int *x;              //最优解数组
int bestp=0;         //最优值初始化为零

//合并函数
void Merge(int left,int mid,int right,Object *array)

{
	Object *temp;
	temp=(class Object*)malloc(sizeof(class Object));
    
	int i=left,j=mid+1,k=0;
	while((i<=mid)&&(j<=right))
		if(array[i].d<=array[j].d) 
		{
			temp[k++]=array[i++];
            //IDtemp[k++]=array[i++].ID;
		}
		else 
		{
			temp[k++]=array[j++];
           // IDtemp[k++]=array[i++].ID;
		}
		while(i<=mid)
		{
			temp[k++]=array[i++];
			// IDtemp[k++]=array[i++].ID;
		}
		while(j<=right)
		{
			temp[k++]=array[j++];
			// IDtemp[k++]=array[i++].ID;
		}
		for(i=0,k=left;k<=right;)
		{
			array[k++]=temp[i++];
		//	array[k++].ID=IDtemp[i++];
		}
}

void Sort(Object *Q,int n)
{
	/*
	int *array,n,x;
	cout<<"输入元素个数："<<endl;
	cin>>n;
	array=new int[n];
	for(int i=0;i<n;i++)
	{
		cout<<"输入第"<<(i+1)<<"个数";
		cin>>x;
		array[i]=x;
	}
	*/
    
   int left,right,mid,size=1;
   //迭代算法
   while(size<n)                             
   {
	   left=0;
	   while(left+size<n)
	   {
		   mid=left+size-1;
		   if(mid+size>n-1)right=n-1;
		   else right=mid+size;
		   Merge(left,mid,right,Q);
		   left=right+1;
	   }
	   size*=2;
   }
/*
   cout<<"\n排序后"<<endl;
   for(i=0;i<n;i++)
  	   cout<<setw(3)<<array[i].id<<array[i].d<<endl;
	   cout<<endl;
 */  


}

int Knapsack(int *p,int *w,int c,int n)
{
	//为Knap::Backtrack 初始化
	int W=0;
	int P=0;
	Object *Q; 
	Q=new Object[n];
	for(int i=0;i<n;i++)
	{
		Q[i].ID=i;
		Q[i].d=1.0*p[i]/w[i];
		P+=p[i];
		W+=w[i];
	}
	if(W<c) 
	{
		for(int i=0;i<n;i++)
			x[i]=1;
		return P;
		
	}//装入所物品
	Sort(Q,n);
	Knap K;
	K.p=new int[n];
	K.w=new int[n];
	for(i=0;i<n;i++)
	{
		K.p[i]=p[Q[i].ID];
		K.w[i]=w[Q[i].ID];
	}
	K.cp=0;
	K.cw=0;
	K.c=c;
	K.n=n;
	K.bestp=0;
	//回溯搜索
	K.Backtrack(0);
	delete[] Q;
	delete[]K.w;
	delete[]K.p;
	return K.bestp;
}

int Knap::Bound(int i)
{
	//计算上界
	int cleft=c-cw;
	int b=cp;
	//以物品单位价值递减序装入物品
	while(i<=n && w[i]<=cleft)
	{
		cleft-=w[i];
		b+=p[i];
		i++;
	}
	//装满背包
	if(i<n) b+=p[i]/w[i]*cleft;
	return b;
}

//最优解
void Knap::Backtrack(int i)
{
	if(i>n)
	{
		bestp=cp;
		return;
	}
	if(cw+w[i]<=c)
	{
		x[i]=1;
		cw+=w[i];
		cp+=p[i];
		Backtrack(i+1);
                cw-=w[i];
		cp-=p[i];
	}
	if(Bound(i)>bestp)
	{
		x[i]=0;
		Backtrack(i+1);
	}
}
void main()
{

	int *p,*w,n,c,j;
	
	cout<<"请输入背包容量:"<<endl;
	cin>>c;
	cout<<"请输入物品个数:"<<endl;
	cin>>n;

	if(n<=0)
		cout<<"数量输入违法!!";
	else if(n==1)
	{
       	cout<<"请输入物品的重量："<<endl;
		cin>>j;
        cout<<"请输入物品的价值："<<endl;
		int k;
		cin>>k;
		if(j<=c)
			bestp=k;
		else bestp=0;
	}
	else
	{
		
	p=new int[n];
	w=new int[n];
	x=new int[n];


	for(int i=0;i<n;i++)
	{
		cout<<"请输入第"<<(i+1)<<"件物品的重量："<<endl;
		cin>>j;
		w[i]=j;
		cout<<"请输入第"<<(i+1)<<"件物品的价值："<<endl;
		cin>>j;
		p[i]=j;
	}
	for(i=0;i<n;i++)
	{
		cout<<p[i]<<endl;
		cout<<w[i]<<endl;
	}

    bestp=Knapsack(p,w,c,n);
	
	cout<<"\n最优解："<<endl;
	for(i=0;i<n;i++)
		cout<<setw(3)<<x[i];
    cout<<endl;
	/*
	delete[] p;
	delete[] w;
	delete[] x;
	*/
	}

	cout<<"\n最优值："<<bestp<<endl;
}