学步园

/*贪心法求解带有期限的作业排序*/
#include <stdlib.h>
#include <stdio.h>

typedef struct _Job
{
    int profit;
    int deadline;
}Job;

Job* JobPatch(Job jobs[],int n)
{   //jobs 已经按照profit从大到小排序
    //贪心法的思想就是按照profit从大大小选择插入到合适位置
    int i,j;
    Job *J = (Job *)malloc(sizeof(Job)*100);
    for(i=0; i<100; i++)
    {
        J[i].deadline = -1;
        J[i].profit = -1;
    }
    for(i=0; i<n; i++)
    {
        for(j=jobs[i].deadline; j>0; j--)
        {
            if(J[j].profit == -1)
            {
                J[j].profit = jobs[i].profit;
                J[j].deadline = jobs[i].deadline;
                break;
            }
        }
    }
    return J;
}
/*打印*/
void print(Job *jobs,int n)
{
    int i = 0,profit=0;
    for(i=0;i<n;i++)
    {
        if(-1 != jobs[i].profit)
        {
            printf("%d\t",jobs[i].profit);
            profit += jobs[i].profit;
        }

    }
    printf("\n\nTotal profit : %d\n",profit);
}
int main(int argc, char *argv[])
{
    Job jobs[] = {{35,4},{30,2},{25,4},{20,3},{15,4},{10,8},{5,3}};
    int n = 7;

    Job *schedule = JobPatch(jobs,n);
    print(schedule,100);
    return 0;
}