首页 > 代码库 > POJ 3181 Dollar Dayz && Uva 147 Dollars（完全背包）
POJ 3181 Dollar Dayz && Uva 147 Dollars（完全背包）
首先是 Uva 147：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83
细心看完这题后发现还是完全背包，只不过需要对浮点数处理一下。即把所有硬币的面值都乘以100，化为整数，对输入的数据也作同样的处理，然后就是套完全背包的模板了，在输出时还要用格式和精度来卡一卡你……一开始我没想到用printf可以的，于是百度了cout的输出格式控制，确实cout的格式和精度控制相比起printf来说都很不方便啊。。。
1 #include<cstdio> 2 #include<iomanip> 3 #include<iostream> 4 using namespace std; 5 typedef long long LL; 6 7 const LL coin[15]= {0,5,10,20,50,100,200,500,1000,2000,5000,10000}; 8 LL f[30010]= {1}; 9 10 inline void init(){11 for(LL i=1; i<=11; ++i)12 for(LL j=coin[i]; j<=30000; ++j)13 f[j]+= f[j-coin[i]];14 }15 16 int main(){17 init();18 double money;19 cout.setf(ios::fixed);20 cout.precision(2);21 while(cin>>money && money!=0.00){22 cout<<setw(6)<<money<<setw(17)<<f[int(money*100+0.5)]<<endl; //这里的money转化为整数时要切记+0.5！防止精度误差！23 }24 return 0;25 }
而用scanf和printf的话只需这么简洁即可：
1 while(scanf("%lf",&money),money!=0.00){2 printf("%6.2f%17lld\n",money,f[int(money*100+0.5)]);3 }
然后是 POJ 3181：http://poj.org/problem?id=3181
虽然还是用硬币作背景，但其实就是整数划分，一开始我数组开小了，结果RE了，后来开大数组后却忘记测试那些强力数据了，到看了别人的博客后才知道会超long long的，我就想难道要用高精度？可别人说直接高精度的话会TLE的，因为测试过最大的数据只是33位而已，所以用两个long long即可，同样式利用高精度的原理来进行加法模拟，要注意一些输出的细节即可：
1 #include<cstdio> 2 #include<cstring> 3 typedef long long LL; 4 const LL largest= 1e17; 5 LL f1[1008], f2[1008]; 6 7 int main(){ 8 int n,k; 9 while(~scanf("%d%d",&n,&k)){10 memset(f2,0,sizeof(f2));11 memset(f1,0,sizeof(f1));12 f2[0]= 1;13 for(int i=1; i<=k; ++i) 14 for(int j=i; j<=n; ++j){15 f1[j]+= f1[j-i];16 f2[j]+= f2[j-i];17 if(f2[j]>=largest){18 f1[j]+= f2[j]/largest;19 f2[j]%= largest;20 }21 }22 if(!f1[n]) printf("%I64d\n",f2[n]);23 else printf("%I64d%017I64d\n",f1[n],f2[n]);24 }25 return 0;26 }
附上kuangbin大神的精辟题解：http://www.cnblogs.com/kuangbin/archive/2012/09/20/2695165.html
POJ 3181 Dollar Dayz && Uva 147 Dollars（完全背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。