knap_2.cpp

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

// 贪婪0/1背包问题算法， 2阶.思想见下面注释中

#include <iostream>
#include "hsort.h"
#include "object2.h"
//#include "knap_0.cpp"
using namespace std;

template<class Tw, class Tp>
float Knapsack(Tp p[], Tw w[], Tw c, int n, int x[] ,int t)
{//对了一个形参t，它是1阶用来先选择排序后第t个元素，然后再在剩下的n-1个元素中应用贪婪算法
   float P = 0;  // will be sum of profits

   // define an object array to be sorted by profit density
   Object *Q = new Object [n+1];

   for (int i = 1; i <= n ; i++)
   {
	   //根据传入的p,w初始化密度
	   Q[i].ID = i;
	   Q[i].d = 1.0*p[i]/w[i];
   }

   // 根据密度排序先
   HeapSort(Q,n);

   //之后，由于每次会被调用，所以每次开始前初始化x[n]为0
   for (i=1;i<=n;i++)
	   x[i]=0;

   //先选取排序后第t个元素，则P,x,c都有一个值了
   P=p[Q[t].ID];
   x[Q[t].ID]=1;
   c-=w[Q[t].ID];
   //然后在剩下的n-1个元素（用i!=t）来控制的，执行0阶选取法
   for (i = n; i > 0 && i!=t; i--)
   {
      int id = Q[i].ID;
      if (w[id] <= c )
	  {//可以装入，置x[id]=1，c-
         x[id] = 1;
         c -= w[id];
		 P+=p[id];
	  }
      else //否则装不了，置x[id]=0
         x[id] = 0;
   }

   delete [] Q;//删除这个中转数组
   return P;
}

template<class Tw, class Tp>
float Knapsack(Tp p[], Tw w[], Tw c, int n, int x[] ,int t, int m)
{
	float P = 0;  // will be sum of profits
	// define an object array to be sorted by profit density
	Object *Q = new Object [n+1];
	for (int i = 1; i <= n ; i++)
	{
		//根据传入的p,w初始化密度
		Q[i].ID = i;
		Q[i].d = 1.0*p[i]/w[i];
	}
	// 根据密度递增排序先
	HeapSort(Q,n);

   //之后，由于每次会被调用，所以每次开始前初始化x[n]为0
   for (i=1;i<=n;i++)
	   x[i]=0;

   //先选取排序后第t,m个元素，则P,x,c都有一个值了
   if(w[Q[t].ID]+w[Q[m].ID]>c){delete [] Q;return 0;}
   P=p[Q[t].ID]+p[Q[m].ID];
   x[Q[t].ID]=x[Q[m].ID]=1;
   c-=w[Q[t].ID]+w[Q[m].ID];
   //然后在剩下的n-1个元素（用i!=t,!=m）来控制的，执行0阶选取法
   for (i = n; i > 0 && i!=t && i!=m; i--)
   {
      int id = Q[i].ID;
      if (w[id] <= c )
	  {//可以装入，置x[id]=1，c-
         x[id] = 1;
         c -= w[id];
		 P+=p[id];
	  }
      else //否则装不了，置x[id]=0
         x[id] = 0;
   }

   delete [] Q;//删除这个中转数组
   return P;
}

template<class Tw, class Tp>
float Knapsack2(Tp p[], Tw w[], Tw c, int n, int x[])//这是真正的2阶选择函数，它通过调用0阶knapstack函数来实现
{
	//调用n次初始集合为1个元素的不同的0阶函数，比较大小。最后再返回那个P值大的0阶函数
	int i,j,flag=1,flag2,flag3;
	float P=Knapsack(p,w,c,n,x,1);
	for(i=2;i<=n;i++)
	{
		float temp=Knapsack(p,w,c,n,x,i);
		if(temp>P)
		{
			P=temp;
			flag=i;
		}
	}
	//再调用初始集合为2个元素的不同的选法，也是比较P值的大小
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			float temp2=Knapsack(p,w,c,n,x,i,j);
			if(temp2>P)
			{
				P=temp2;
				flag=-1;
				flag2=i;
				flag3=j;
			}
		}
	if(flag==1)
		return Knapsack(p,w,c,n,x,1);
	else if(flag==-1)
		return Knapsack(p,w,c,n,x,flag2,flag3);
	else
		return Knapsack(p,w,c,n,x,flag);
}

void main(void)
{
   int p[5] = {0, 6, 10, 12, 13};
   int w[5] = {0, 2, 4, 6, 7};
   int x[5];
   int n = 4;
   int c = 11;
   cout << "Optimal value is" << endl;
   cout << Knapsack2(p,w,c,n,x) << endl;
   cout << "x vector is" << endl;
   for (int i = 1; i <= 4; i++)
      cout << x[i] << "  ";
   cout << endl;
}