HDU 最大報銷額 (0 1 背包)

最大報銷額

Time Limit : 1000/1000ms (Java/Other)???Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 29???Accepted Submission(s) : 11

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

?

Source

浙大計算機研究生復試上機考試-2007年

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;double dp[40],money[40];int main(){//freopen("input.txt","r",stdin);double Q,a,b,c;int n;while(~scanf("%lf%d",&Q,&n) && n){memset(money,0,sizeof(money));int cnt=0,k;char ch;double num;for(int i=0;i<n;i++){scanf("%d",&k);int flag=1;a=b=c=0;for(int j=0;j<k;j++){getchar();scanf("%c:%lf",&ch,&num);if(num>600)flag=0;if(flag){if(ch=='A')a+=num;else if(ch=='B')b+=num;else if(ch=='C')c+=num;elseflag=0;}}if(flag && a<=600 && b<=600 && c<=600 && (a+b+c)<=1000){money[cnt++]=a+b+c;}}memset(dp,0,sizeof(dp));for(int i=0;i<cnt;i++)for(int j=cnt;j>=1;j--)if((dp[j-1]+money[i]<=Q))   //改成這樣可優化時間 if(j==1 || (dp[j-1]>0 && dp[j-1]+money[i]<=Q))dp[j]=max(dp[j],dp[j-1]+money[i]);double ans=0;for(int i=0;i<=cnt;i++)if(ans<dp[i])ans=dp[i];printf("%.2lf\n",ans);}return 0;
}

?

?