+ -
当前位置:首页 → 问答吧 → 带有限期和效益的单位时间的作业排序-----贪心算法,求指教

带有限期和效益的单位时间的作业排序-----贪心算法,求指教

时间:2011-09-01

来源:互联网

C/C++ code

#include <iostream>
using namespace std;
void SortValue(int time[],int value[],int n)
{
    int temp1,temp2;
    for(int i=1;i<=n;++i)
    {
       for(int j=1;j<=n-i;++j)
       {
            if(value[j]<value[j+1])
            {
                temp1=value[j];
                value[j]=value[j+1];
                value[j+1]=temp1;
                temp2=time[j];
                time[j]=time[j+1];
                time[j+1]=temp2;
            }
       }
    }
}
void js(int arrayp[],int arrayd[],int n)
{
    int r,k,m;
    int a=0;
    arrayp[0]=0;
    arrayd[0]=0;
    int J[100];
    J[0]=0;
    k=1;
    J[1]=1;
    for(int i=2;i<=n;i++)
    {
        r=k; 
        while((arrayd[J[r]]>arrayd[i])&&(arrayd[J[r]]!=r))
            r=r-1;
        if((arrayd[J[r]]<=arrayd[i])&&(arrayd[i]>r))
        {
            for(int p=k;p>=r+1;p--)
                J[p+1]=J[p];
            J[r+1]=i;//关键是这里,为什么最终输出的顺序不是最初的顺序 很郁闷。。。。求高手
            k=k+1;
        }
    }
    cout<<"结果:";
    for(int i=1;i<=k;i++)
        cout<<J[i]<<" ";
    cout<<endl;
}
int main()
{
   int n;
   int Time[100];
   int Value[100];
   int order[100];
   cout<<"输入作业个数:";
   cin>>n;
   cin.clear();
   cout<<"输入每个作业的时间截至:";
   for(int i=1;i<=n;++i)
   {
        cin>>Time[i];
        cin.clear(); 
    } 
    cout<<"输入每个作业的效益值:";
   for(int i=1;i<=n;++i)
   {
        cin>>Value[i];
        cin.clear(); 
    } 
   SortValue(Time,Value,n);
   for(int i=1;i<=n;++i)
   {
      cout<<Value[i]<<"\t";
   }
   js(Time,Value,n);
 
   system("pause");
   return 0;
}

作者: zanglengyu   发布时间: 2011-09-01

学习一下。

作者: asmlearn   发布时间: 2011-09-02