这道题算是一道很经典的题，很好的诠释了贪心和动态规划的不同功能。求最少钱的数量用贪心就够了，但是求最多钱的数量要用到动态规划的思想，每步都尽量保留最大
数量。具体看程序注解：
#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"cmath"
using namespace std;
int fewest(int a[],int num[],int price)
{
int i;
int ans=;
for(i=;i>;i--)
{
if(price>=num[i]*a[i])
{
ans+=num[i];
price-=num[i]*a[i];
}
else
{
ans+=price/a[i];
price%=a[i];
}
}
if(price>num[])return -;
else return ans+price;
}
//这个函数的整体思想就是先保留全部的小钱，用大钱补缺，这样就可以得到最大数量
int largest(int a[],int num[],int price)
{
int i;
int ans=;
int sum[];
sum[]=num[];
for(i=;i<;i++)
{
sum[i]=sum[i-]+a[i]*num[i];
}
for(i=;i>;i--)
{
if(price<=sum[i-])continue;
else
{
int t;
//先用满足条件的最大面值，如果有余数，所用张数+1，
//不足的部分用较小面值的进行补
t=((price-sum[i-])/a[i])+(((price-sum[i-])%a[i])?:);
ans+=t;
price-=t*a[i];
}
}
return ans+price;
}
int main()
{
int t,price,i,j;
int a[]={,,,,,};//面值
int num[];//数量
cin>>t;
while(t--)
{
cin>>price;
int sum=;
for(i=;i<=;i++)
{
cin>>num[i];
sum+=num[i]*a[i];
}
if(sum<price) {cout<<"-1 -1"<<endl;continue;}
int mi=fewest(a,num,price);
if(mi==-) {cout<<"-1 -1"<<endl;continue;}
int mx=largest(a,num,price);
cout<<mi<<" "<<mx<<endl;
}
return ;
}