首页 > 代码库 > hdu 1864 最大报销额 模型为简单的01背包
hdu 1864 最大报销额 模型为简单的01背包
很简单的01背包,但是题目还是很蛋疼的注意题目中600,和1000这两个数,还有就是double和int的转换,1A了感觉还是不错的
/************************************************************************* > File Name: hdu1864.cpp > Author: yang > Mail:826123027@qq.com > Created Time: 2014年08月23日 星期六 14:03:05 ************************************************************************/ #include<iostream> #include<stdio.h> #include<stdlib.h> #include<memory.h> using namespace std; #define N 3000100 int dp[N]; int main(){ // freopen("in.txt","r",stdin); double q; int n; int sum[35]; while(cin>>q>>n,n){ memset(sum,0,sizeof(sum)); q*=100; (int) q; for(int i=0;i<n;i++){ int t; double p; char a,b; cin>>t; int sum_type[3]; int p_sum=0; int flag=0; memset(sum_type,0,sizeof(sum_type)); while(t--){ cin>>a>>b>>p; p=p*100; (int) p; p_sum+=p; // cout<<"p_sum:"<<p_sum<<endl; if(a=='A') sum_type[0]+=p; if(a=='B') sum_type[1]+=p; if(a=='C') sum_type[2]+=p; if(a=='X') { flag=1; break; } } for(int j=0;j<3;j++) if(sum_type[j]>60000) flag=1; if(p_sum>100000) flag=1; if(flag==1) sum[i]=0; else sum[i]=p_sum; // cout<<"sun[i]"<<sum[i]<<endl; } memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++){ for(int j=q;j>=sum[i];j--){ dp[j]=max(dp[j],dp[j-sum[i]]+sum[i]); } } printf("%.2lf\n",dp[(int)q]/100.0); } }
hdu 1864 最大报销额 模型为简单的01背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。