我用的是C,经分析凑n元应该大部分用十一元的,因此一元最多用4张(5张就被1张五元替了)五元最多用4张(同理),而且十一元的张数不会少于n/11-2,不会多于int(n/11),我用的是有限遍历找出所有可能中最少的张数,应该是用时和空间常规方法中最少的,代码如下:
#include <stdio.h>
int main()
{
int a,b,c,n,x,y,t1,t2=2000000;
scanf("%d",&n);
x=int(n/11)+1;
for (a=0;a<5;a++)
for(b=0;b<5;b++)
for(c=x-2;c<x;c++)
{
if (a+b5+c11==n)
{
t1=a+b+c;
if (t1<t2) t2=t1;
}
}
printf("%d",t2);
return 0;
}