话说今天做背包做到有点累了，题目是英文的……而且还很长，我看了好久（弱爆了）。
题目大概的意思就是，有六种硬币，之后，求用这六种硬币最小数目支付1到100美分的平均值，以及最小数目中的最大值。
很容易就想到了不找零的情况。即：1 2 5 45 50 60 六种硬币中，我买了49分，那么应该就是45 +2+2 3个硬币，但是有找零情况下就是50 -1。
这就头痛了，我在想，要不加入硬币为负数吧，想了一下，感觉有点吃力？!
后来，听别人说，两次完全背包就好了，之后我就很兴奋地试验了一下，结果发现，真的OK。案例数据很轻松就OK了。
一交，果断就WA了。！！！！！！
一看，是输出时候只是一个空格，我删了一个，又交！
还是WA了！
这下就郁闷了，无奈之下只能看discuss了。别人给了一个数据，一测，果然错了，
1 95 96 97 98 99
说是dp不能只是100,要到2000……一看，真有道理啊。
/*******************************************************************************/
/* OS : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
* Compiler : g++ (GCC) 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
* Encoding : UTF8
* Date : 2014-03-09
* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/ #include <iostream>
#include <cstdio>
#include <iomanip> using namespace std;
int dp[2001];
int c[40],w[40];
int min(int a,int b){
return a>b?b:a;
}
int main(){
// freopen("in.txt","r",stdin);
int cases,N,i,j,mi=0;
double sum;
cin>>cases;
while(cases--){
sum=0;
N=2000;
mi=0;
for(i=1;i<=6;i++){
cin>>c[i]; } //初始化
for(i=1;i<=2000;i++)
dp[i]=20000; dp[0]=0; //第一次完全背包
for(i=1;i<=6;i++)
for(j=c[i];j<=N;j++)
dp[j]=min(dp[j],dp[j-c[i]]+1); //第二此完全背包 ,找零
for(i=1;i<=6;i++)
for(j=N-c[i];j>=0;j--)
dp[j]=min(dp[j],dp[j+c[i]]+1); for(i=1;i<=100;i++){
sum+=dp[i];
if(dp[i]>mi){
mi=dp[i];
}
}
cout<<setprecision(2)<<std::fixed<<(sum/100.0)<<" "<<mi<<endl; }
// fclose(stdin); return 0;
}