最大報銷額 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;
}
