knap_1.cpp

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

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

#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 Knapsack1(Tp p[], Tw w[], Tw c, int n, int x[])//这是真正的1阶选择函数，它通过调用0阶knapstack函数来实现
{//调用n次不同的0阶函数，比较大小。最后再返回那个P值大的0阶函数
	int i,flag=1;
	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;
		}
	}
	if(flag==1)
		return Knapsack(p,w,c,n,x,1);
	else
		return Knapsack(p,w,c,n,x,flag);
}

int main()
{
	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 << Knapsack1(p,w,c,n,x) << endl;
    cout << "x vector is" << endl;
    for (int i = 1; i <= 4; i++)
		cout << x[i] << "  ";
    cout << endl;

	return 0;
}