先计算6种钱币相加的情况，有f[j] = min(f[j], f[j-data[i]]+1) ;

然后计算找零的情况，有f[j] = min(f[j], f[j+data[i]]+1) ;

计算的上限要比100大，因为有找零的情况，但是要大多少不太好确定。

code:

#include<cstdio>

#include<cstring>

#include<algorithm>

using 

namespace std ;

const 

int Max = 

2500 ;

//

..

int data[

6], f[Max] ;

int main(){

    

int t, n, i, j, sum, max ;

    scanf(

"

%d

", &t) ;

    

while(t--){

        

for(i=

0; i<

6; i++)

            scanf(

"

%d

", &data[i]) ;

        f[

0] = 

0 ;

        

for(i=

1; i<Max; i++)

            f[i] = 

2000000 ;

        

for(i=

0; i<

6; i++)      

//

相加

            

for(j=data[i]; j<Max; j++)

                f[j] = min(f[j], f[j-data[i]]+

1) ;

        

for(i=

0; i<

6; i++)      

//

相减

            

for(j=Max-data[i]; j>=

1; j--)

                f[j] = min(f[j], f[j+data[i]]+

1) ;

        sum = max = 

0 ;

        

for(i=

1; i<=

100; i++){

            sum += f[i] ;

            

if(f[i]>max)    max = f[i] ;

        }

        printf(

"

%.2lf %d\n

", (

double)sum/

100, max) ;

    }

    

return 

0 ;}