学步园

题意：给6种不同币值的钱，求从【1,100】各个值用最少的硬币组成这些值

例如

1 2 5 10 20 50

68=50+20-1-1 四个

思路：多次完全背包或（加钱完全背包一次，再找零背包一次），ps：背包的大小不是100，应该2000左右（因为可以找零

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define CL(a,b) memset(a,b,sizeof(a))
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
#define INF 0x7ffffff
using namespace std;
const int M(2000);
int ff[M],a[10];
int main()
{
	int t,i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		for(i=0;i<6;i++)
			scanf("%d",&a[i]);
		for(i=0;i<M;i++)
			ff[i]=INF;
		ff[0]=0;
		for(k=0;k<15;k++)//多次完全背包，15次就可以过这题
		{
			for(i=0;i<6;i++)
			{
				for(j=0;j<M;j++)
				{
					if(j-a[i]>=0)
						ff[j]=MIN(ff[j-a[i]]+1,ff[j]);
					if(j+a[i]<M)
						ff[j]=MIN(ff[j+a[i]]+1,ff[j]);
				}
			}
		}

		/*
		for(i=0;i<6;i++)
		// 两次背包
 {for(j=0;j<M;j++){if(j-a[i]>=0)ff[j]=MIN(ff[j-a[i]]+1,ff[j]);}}for(i=0;i<6;i++)for(j=M-1;j>=0;j--)if(j+a[i]<M)ff[j]=MIN(ff[j+a[i]]+1,ff[j]);*///printf("\n");int sum=0,maxm=0;for(i=0;i<101;i++){sum+=ff[i];// printf("(%d,%d) ",i,ff[i]);maxm=MAX(maxm,ff[i]);}//

 printf("\n");printf("%.2lf %d\n",(double)sum/100.0,maxm);}}