题目链接：

DP题目，背包问题，我们的背包容量为输入的Q，物品的数目使我们输入的N，需要注意的有3个点：

1）物品的种类只能是A、B、C，其他的物品不予报销

2）单个物品种类不能超过600

3）单张发票上可以有多个种类，但是不能超过1000

考虑到这些，注意一些需要处理的细节，如字符的处理等，采用DP策略即可。置初始化dp[0] = 0,表示都没有报销，外层循环遍历后续的发票，内层循环遍历当前发票之前的发票，判定如果报销发票满足输入能报销的最大额，就加上。最后遍历一遍DP数组，取最大值便是最优解。代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 //#include
         
           6 const int maxn = 35; 7 using namespace std; 8  9 int main(){10     int i,j,n,num,flag,cnt;11     double dp[maxn],m[maxn];12     char str,b;13     double w,f;14     double A,B,C,MAX;15     while(cin >> w >> n && n){16         memset(dp,0,sizeof(dp));17         cnt = 1;18         for(i = 0; i < n; i++){19             flag = 0;20             A = 0;21             B = 0;22             C = 0;23             cin >> num;24             for(j = 0; j < num; j++){25                 cin >> str >> b >> f;26                 if(str == 'A'){27                     A += f;28                 }29                 else if(str == 'B'){30                     B += f;31                 }32                 else if(str == 'C'){33                     C += f;34                 }35                 else{36                     flag = 1;37                 }38             }39             if(!flag && A <= 600 && B <= 600 && C <= 600 && A+B+C <= 1000){40                 m[cnt++] = A+B+C;41             }42         }43         for(i = 1; i < cnt; i++){44             for(j = i-1; j >= 0; j--){45                 if(dp[j]+m[i] <= w){46                     dp[i] = max(dp[j]+m[i],dp[i]);47                 }48             }49         }50         MAX = 0;51         for(i = 0; i < cnt; i++){52             if(dp[i] > MAX){53                 MAX = dp[i];54             }55         }56         printf("%.2lf\n",MAX);57     }58     return 0;59 }