话说今天做背包做到有点累了,题目是英文的……而且还很长,我看了好久(弱爆了)。
题目大概的意思就是,有六种硬币,之后,求用这六种硬币最小数目支付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; }