#include <stdio.h>

#include <malloc.h>

void  sort(int *P,int *D,int n)

{              //將作業按效益值非遞增次序排序

int i,k,t;

for(k=1;k<n;++k)

for(i=k+1;i<=n;++i)

if(P[k]<P[i])

{

t=P[k];

P[k]=P[i];

P[i]=t;

t=D[k];

D[k]=D[i];

D[i]=t;

}

}

void JS(int *D,int *P,int *J,int n)

{     //J[i]是最優解中的第i個作業，終止時最優解中的作業的期限值按非遞減次序排序

int i,j,k,r;

sort(P,D,n);

k=1;

J[1]=1;    //計入作業1

for(i=2;i<=n;++i)//按p的非增次序考慮作業。找i的位置并檢查插入的可行性

{

r=k;

while((D[J[r]]>D[i])&&(D[J[r]]!=r))

--r;
if((D[J[r]]<=D[i])&&(D[i]>r))

{           //把i插入J

for(j=k;j>=r+1;--j)

J[j+1]=J[j];

J[r+1]=i;

k++;

}

}

printf("最優解為:");

printf("\n");

for(i=1;i<=k;++i)

{         //按順序輸出最優解中作業的期限值和效益值

printf("第%d個作業的期限值為%d，效益值為%d",i,D[J[i]],P[J[i]]);

printf("\n");

}

}

void main()

{

int n,j;

printf("請輸入作業的個數:");

scanf("%d",&n);

int *D,*P,*J;

D=(int *) malloc(sizeof(int *)(n+1));

P=(int *) malloc(sizeof(int *)(n+1));

J=(int *) malloc(sizeof(int *)(n+1));

D[0]=P[0]=J[0]=0;  //初始化

printf("請輸入每個作業的效益值：");

for(j=1;j<=n;j++)

scanf("%d",&P[j]);

printf("請輸入每個作業的期限值：");

for(j=1;j<=n;j++)

scanf("%d",&D[j]);

JS(D,P,J,n);     //

}