#include<stdio.h>
#include<stdlib.h>
#include<time.h>
long F[10000]={0};
long count1=0,count2=0,count3=0,count4=0;
void CoinRow(long *c,long n)//币值最大化的动态规划
{
F[0]=0;
F[1]=c[1];
for(long i=2;i<=n;i++)
{
F[i]=(c[i]+F[i-2])>F[i-1]?(c[i]+F[i-2]):F[i-1];
count1++;
}
}
long CoinRow1(long *c,long n) //币值最大化的递归算法
{
count2++;
long temp1,temp2;
if(n==0)
F[n]=0;
else if(n==1)
F[n]=c[1];
else
{
temp1=c[n]+CoinRow1(c,n-2);
temp2=CoinRow1(c,n-1);
F[n]=temp1>temp2?temp1:temp2;
}
return F[n];
}
void yesangeMaking(long *D,long n,long m) //找零问题的动态规划
{
long temp;
long j;
F[0]=0;
for(long i=1;i<=n;i++)
{
temp=100000;
j=1;
while(j<=m&&i>=D[j])
{
count3++;
temp=F[i-D[j]]<temp?F[i-D[j]]:temp;
j=j+1;
}
F[i]=temp+1;
}
}
long yesangeMakingDG(long *D,long n,long m)
{
long j,s,temp;
if(n==0)
F[n]=0;
else
{
temp=1000000;
j=1;
while(j<=m&&n>=D[j])
{
(count4)++;
s=yesangeMakingDG(D,n-D[j],m);
temp=s<temp?s:temp;
j+=1;
}
F[n]=temp+1;
}
return F[n];
}
void no()
{
clock_t start;
clock_t finish;
double totaltime1,totaltime2;
long i,n;
long c[10000]={0};
printf("请输入硬币的总个数:");
scanf("%ld",&n);
fflush(stdin);
for(i=1;i<=n;i++)
c[i]=c[i-1]+rand()%10;
printf("币值最大化动态规划\n");
printf("硬币个数 运行次数 运行时间\n");
for(i=1;i<=n;i++)
{
count1=0;
start=clock();
CoinRow(c,i); //动态规划
finish=clock();
totaltime1=(double)(finish-start)/CLOCKS_PER_SEC;
printf(" %d\t\t%d\t\t%10lf\n",i,count1,totaltime1);
}
printf("币值最大化递归算法\n");
printf("硬币个数 运行次数 运行时间\n");
for(i=1;i<=n;i++)
{
count2=0;
start=clock();
CoinRow1(c,i);
finish=clock();
totaltime2=(double)(finish-start)/CLOCKS_PER_SEC;
printf(" %d\t\t%d\t\t%10lf\n",i,count2,totaltime2);
}
}
void yes()
{
long c[10000]={0};
c[1]=1;
long n,m,i;
clock_t start;
clock_t finish;
double totaltime3,totaltime4;
srand(time(NULL));
printf("请输入要找零的金额:");
scanf("%ld",&n);
printf("请输入要硬币的总个数:");
scanf("%ld",&m);
fflush(stdin);
for(i=2;i<=m;i++)
c[i]=c[i-1]+rand()%2+2;
printf("找零问题动态规划\n");
printf("硬币个数 运行次数 运行时间\n");
for(i=1;i<=m;i++)
{
count3=0;
start=clock();
yesangeMaking(c,i,n);
finish=clock();
totaltime3=(double)(finish-start)/CLOCKS_PER_SEC;
printf(" %d\t\t%d\t\t%10lf\n",i,count3,totaltime3);
}
printf("找零问题递归算法\n");
printf("硬币个数 运行次数 运行时间\n");
for(i=1;i<=m;i++)
{
count4=0;
start=clock();
yesangeMakingDG(c,i,n);
finish=clock();
totaltime4=(double)(finish-start)/CLOCKS_PER_SEC;
printf(" %d\t\t%d\t\t%10lf\n",i,count4,totaltime4);
}
}
void main()
{
// no();
yes();
}