最大報銷額 Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) Total Submission(s) : 14 Accepted Submission(s) : 2 Problem Description 現有一筆經費可以報銷一定額度的發票。允許報銷的發票類型包括買圖書(A類)、文具(B類)、差旅(C類),要求每張發票的總額不得超過1000元,每張發票上,單項物品的價值不得超過600元。現請你編寫程序,在給出的一堆發票中找出可以報銷的、不超過給定額度的最大報銷額。 Input 測試輸入包含若干測試用例。每個測試用例的第1行包含兩個正數 Q 和 N,其中 Q 是給定的報銷額度,N(<=30)是發票張數。隨後是 N 行輸入,每行的格式為: m Type_1:price_1 Type_2:price_2 ... Type_m:price_m 其中正整數 m 是這張發票上所開物品的件數,Type_i 和 price_i 是第 i 項物品的種類和價值。物品種類用一個大寫英文字母表示。當N為0時,全部輸入結束,相應的結果不要輸出。 Output 對每個測試用例輸出1行,即可以報銷的最大數額,精確到小數點後2位。 Sample Input 200.00 3 2 A:23.50 B:100.00 1 C:650.00 3 A:59.99 A:120.00 X:10.00 1200.00 2 2 B:600.00 A:400.00 1 C:200.50 1200.50 3 2 B:600.00 A:400.00 1 C:200.50 1 A:100.00 100.00 0 Sample Output 123.50 1000.00 1200.50 題意:先給出最大的報銷額和發票的張數,然後下面是n張發票,每張發票先給出發票上物品的個數,然後給出每種物品和物品的價格 注意:1.只有a,b,c三種物品可以報銷,含有其他物品的發票作廢 2.單件物品的價值不能超過600 3.每張發票總價值不能超過1000 輸出最大價值 思路:也是一道01背包果題,知道了條件之後要寫也不是難事 代碼: 下面的代碼是錯的,不能通過,不知道為什麼,我是按照題意做的
#include<iostream> #include<stdio.h> #include<cstring> using namespace std; int dp[3100000]; int w[1000]; int get_max(int a,int b){ return a>b?a:b; } int main(){ double Q; int N,m,count,i,j,sum,a; bool use; while(scanf("%lf%d",&Q,&N)&&N){ count=0; memset(dp,0,sizeof(dp)); for(i=0;i<N;i++){ scanf("%d",&a); use=true; sum=0; for(j=0;j<a;j++){ char type,temp1,temp2; double price; temp1=getchar();type=getchar();temp2=getchar(); cin>>price; sum+=price*100; if(type<'A'||type>'C'||price>600||sum>100000) use=false; } if(use) w[count++]=sum; } int t=Q*100; for(i=0;i<count;i++) for(j=t;j>=w[i];j--) dp[j]=get_max(dp[j],dp[j-w[i]]+w[i]); double ans=(double)dp[t]/100; printf("%.2lf\n",ans); } return 0; } #include<iostream> #include<stdio.h> #include<cstring> using namespace std; int dp[3100000]; int w[1000]; int get_max(int a,int b){ return a>b?a:b; } int main(){ double Q; int N,m,count,i,j,sum,a; bool use; while(scanf("%lf%d",&Q,&N)&&N){ count=0; memset(dp,0,sizeof(dp)); for(i=0;i<N;i++){ scanf("%d",&a); use=true; sum=0; for(j=0;j<a;j++){ char type,temp1,temp2; double price; temp1=getchar();type=getchar();temp2=getchar(); cin>>price; sum+=price*100; if(type<'A'||type>'C'||price>600||sum>100000) use=false; } if(use) w[count++]=sum; } int t=Q*100; for(i=0;i<count;i++) for(j=t;j>=w[i];j--) dp[j]=get_max(dp[j],dp[j-w[i]]+w[i]); double ans=(double)dp[t]/100; printf("%.2lf\n",ans); } return 0; }
網上找了一下原因,發現要把發票分開報銷,搞不懂為什麼,發票能分開報銷麼。。。就是一張發票只報銷一部分。。。望知道的告訴我一聲 代碼:
#include<stdio.h> #include<string.h> int N,i,j,t,num,k,q; double Q,s; char ch[20]; int f[3100000],w[1000],temp[31],sum,m[3]; int main() { while(scanf("%lf %d",&Q,&N)==2) { if(N==0) break; t=0; q=(int)(Q*100); memset(f,0,sizeof(f)); while(N--) { scanf("%d",&k); memset(temp,0,sizeof(temp)); memset(m,0,sizeof(m)); for(i=0;i<k;i++) { memset(ch,'\0',sizeof(ch)); getchar(); scanf("%s",ch); num=strlen(ch); for(j=2;j<num;j++) { if(ch[j]=='.') continue; temp[i]=10*temp[i]+(ch[j]-'0'); } if(ch[0]=='A') m[0]+=temp[i]; if(ch[0]=='B') m[1]+=temp[i]; if(ch[0]=='C') m[2]+=temp[i]; } if(ch[0]>='A' && ch[0]<='C' && m[0]<=60000 && m[1]<=60000 && m[2]<=60000 && (m[0]+m[1]+m[2])<=100000) { for(i=0;i<k;i++) { w[t++]=temp[i]; printf("w[%d]=%d\n",t-1,w[t-1]); } } } for(i=0;i<t;i++) { for(j=q;j>=w[i];j--) f[j]=(f[j] > f[j-w[i]]+w[i] ? f[j] : f[j-w[i]]+w[i]); } s=(double)f[q]/100; printf("%.2lf\n",s); } return 0; } #include<stdio.h> #include<string.h> int N,i,j,t,num,k,q; double Q,s; char ch[20]; int f[3100000],w[1000],temp[31],sum,m[3]; int main() { while(scanf("%lf %d",&Q,&N)==2) { if(N==0) break; t=0; q=(int)(Q*100); memset(f,0,sizeof(f)); while(N--) { scanf("%d",&k); memset(temp,0,sizeof(temp)); memset(m,0,sizeof(m)); for(i=0;i<k;i++) { memset(ch,'\0',sizeof(ch)); getchar(); scanf("%s",ch); num=strlen(ch); for(j=2;j<num;j++) { if(ch[j]=='.') continue; temp[i]=10*temp[i]+(ch[j]-'0'); } if(ch[0]=='A') m[0]+=temp[i]; if(ch[0]=='B') m[1]+=temp[i]; if(ch[0]=='C') m[2]+=temp[i]; } if(ch[0]>='A' && ch[0]<='C' && m[0]<=60000 && m[1]<=60000 && m[2]<=60000 && (m[0]+m[1]+m[2])<=100000) { for(i=0;i<k;i++) { w[t++]=temp[i]; printf("w[%d]=%d\n",t-1,w[t-1]); } } } for(i=0;i<t;i++) { for(j=q;j>=w[i];j--) f[j]=(f[j] > f[j-w[i]]+w[i] ? f[j] : f[j-w[i]]+w[i]); } s=(double)f[q]/100; printf("%.2lf\n",s); } return 0; }