knap_0.cpp

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

// 贪婪0/1背包问题算法， 0阶

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

template<class Tw, class Tp>//传入的p[],w[]类型可能不同，所以要两个
float Knapsack(Tp p[], Tw w[], Tw c, int n, int x[])
{//返回最优装载值
 //如果物品i可装入，则设置x[i] = 1，1 <= i <= n.
	float P = 0;  // 价值之和
	
	//定义一个对象数组，它是按价值密度递减排序的
	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);
	
	//按密度递减装载
	for (i = n; i > 0; i--)	
	{
		int id = Q[i].ID;
		if (w[id] <= c )
		{//可以装入，置x[id]=1，c-,同时总价值P+
			x[id] = 1;
			c -= w[id];
			P += p[id];
		}
		else //否则装不了，置x[id]=0
			x[id] = 0;
	}
	
	delete [] Q;//删除这个中转数组
	return P;
}

int main()
{
	int p[6] = {0, 6, 3, 5, 4, 6};
    int w[6] = {0, 2, 2, 6, 5, 4};
    int x[6];
    int n = 5;
    int c = 10;
    cout << "Optimal value is" << endl;
    cout << Knapsack(p,w,c,n,x) << endl;
    cout << "x vector is" << endl;
    for (int i = 1; i <= 5; i++)
		cout << x[i] << "  ";
	cout << endl;
	return 0;
}