cload.cpp

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

// 贪婪算法之货箱装船，这里利用了间接寻址排序函数InderectSor来对Weight进行排序（当然也可利用堆排序了）
//注：书中给的答案，Inderectsort有误，这里还是选用堆排序

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

/*void IndirectSort(int w[], int t[], int n)
{//根据间接表，需要一个指针表，而这里t[i]即为一个指针，用来指向w中的第i元素
   for (int i=1; i <= n; i++) t[i] = i;
}*/

template<class T>
void ContainerLoading(int x[],  T w[], T c, int n)
{//x[i]=1当且仅当货箱i被装载，1<= i<= n,c是船的容量，w是货箱的重量

   HeapSort(w,n);
 
   int i;
   for(i=1;i<=n;i++)
	   cout<<w[i]<<' ';
   cout<<endl;
   
   // 初始化x
   for (i = 1; i <= n; i++)
      x[i] = 0;
   
   // 按照重量顺序选择物品
   for (i = 1; i <= n && w[i] <= c; i++)
   {
	   x[i] = 1;
	   c -= w[i];
   } 
   
   //delete [] t;
}

int main()
{
   int w[9] = {0, 100, 50, 90, 200, 50 , 20, 150, 80 }, x[9];
   ContainerLoading(x, w, 400, 8);
   cout << "Loading vector is" << endl;
   for (int i = 1; i <= 8; i++)
      cout << x[i] << ' ';
   cout<<"\nThese Bins with weight are moved to the boat:\n";
   for (i=1;i<=8;i++)
   {
	   if(x[i]!=0)
		   cout<<w[i]<<' ';
   }
   cout << endl;
   return 0;
}