greedy.cpp

贪心算法求磁盘最优存储问题,能够解决此问题.不失为一种好办法.

// greedy.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
int partition(double a[],int p,int r,int b[])
{
	int i=p,j=r+1;
	double t;
	int t1;
	double x=a[p];
	int	y=b[p];
	while(1){
		 while(a[++i]<x) ;
		 while(a[--j]>x) ;
		 if(i>=j) break;
		 t=a[i];
		 a[i]=a[j];
		 a[j]=t;
	     t1=b[i];
		 b[i]=b[j];
		 b[j]=t1;
	}
	a[p]=a[j];
    b[p]=b[j];
	a[j]=x;
	b[j]=y;
	return j;
}
void quicksort(double a[],int p,int r,int b[])
{
	if (p<r){
		int q=partition(a,p,r,b);
		quicksort(a,p,q-1,b);
		quicksort(a,q+1,r,b);
	}
}
void greedy(double p[],double d[][4],int n)
{
	int i,j;
	double *a=new double [n];
    double *b=new double [n];
    int *t1=new int [n];
    int *t2=new int [n];
	for(i=0;i<n;i++)
		a[i]=p[i]*(1-p[i]);
	for(i=0;i<n;i++)
		b[i]=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			b[i]+=d[i][j];
	for(i=0;i<n;i++)
	{ t1[i]=i;
	  t2[i]=i;
	}
	quicksort(a,0,n-1,t1);
	quicksort(b,0,n-1,t2);
	
	int *c=new int[n];
	cout<<"start:"<<endl;
	for(i=0;i<n;i++)
	{	
		c[t2[i]]=t1[n-i-1];
	}
	for(i=0;i<n;i++)
		cout<<"第"<<i<<"磁道放第"<<c[i]<<"个文件"<<endl;
}

void main()
{
	double p[4]={0.4,0.2,0.1,0.3};
	double d[4][4]={0.0,15.0,13.0,5.0,15.0,0.0,7.1,8.9,13.0,7.1,0.0,10.2,5.0,8.9,10.2,0.0};
	greedy(p,d,4);
}