算法设计与分析背包问题及作业排序
一．源程序：
/* 背包问题的递归算法*/
#include
#include
int knap(int s,int n);
int* w;
int knap(int s,int n)
{
if ( s == 0 )
return (1);
else if ((s<0)||((s>0)&&(n<1)))
return(0);
else if ( knap(s - w[n-1],n - 1)==1 )
{
printf("result: n=%d ,w[%d]=%d \n",n,n-1,w[n-1]);
return (1);
}
else
return ( knap(s,n - 1) );
}
main()
{
int s=0,n=0,result=0,i=0;
printf("please input s=");/*输入s*/
scanf("%d",&s);
printf("please input n=");/*输入n*/
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("please input the %d numbers(weight):\n",n);/*输入重量*/
for(i=0;i scanf("%d",w+i);
result=knap(s,n);
if(result==0)
printf("no solution!\n");
return 0;
}
//作业排序
#include "iomanip.h"
#include
void JOB_S(int n,int *D);
void JOB_S(int n,int *D)
{
int i,k,r;
int *J=new int[n+1];
k=1;
D[0]=0;
J[0]=0;
J[1]=1;
for(i=2;i<=n;i++)
{
r=k;
while(D[J[r]]>D[i] && D[J[r]]!=r)
r=r-1;
if(D[J[r]]<=D[i] && D[i]>r)
{
for(int x=k;x>=r+1;x--)
J[x+1]=J[x];
J[r+1]=i;
k++;
}
}
cout<<"该作业的最优处理顺序为:";
for(i=1;i<=k;i++)
cout< cout<}
void main()
{
int *D,*P; //定义变量数组，采用动态分配内存
int i,n;
cout<<"请输入要处理的作业数n:";
cin>>n;
D=new int[n+1]; //作业的截止期限数组
P=new int[n+1]; //作业的效益数组
cout<<"请输入作业i的期限值D(1-"< for(i=1;i<=n;i++)
{
cout<<"作业"< cin>>D[i];
}
cout< cout<<"请输入作业i的效益值P(1-"< for(i=1;i<=n;i++)
{
cout<<"作业"< cin>>P[i];
}
cout< JOB_S(n,D);
}
二．流程图找站长QQ3710167
1．背包问题
三．心得体会 通过此次上机实验，发现自己编程能力不强，有待提高，今后要多加练习。
