![勾选C++才能过
题意：
先规定可以报销一定额度的发票，物品类型有A，B，C，三种。要求每张发票总额不得超过1000元，单项物品不得超过600.求报销的最大额
分析：
先找到合格的发票，然后再挑选总额最大的几张发票（01背包来解决）
如何找出合格发票？
1.发票中只有ABC着三种物品
2.单张发票的额度<=1000.
3.一张发票中，单项物品总额<=600
题目中的价钱都是浮点数，01背包只能处理整数，怎么办？
题目给的数据最多两位数（题目没说保留几位小数），所以我们可以把数据都*100，等用01背包的方法计算完后，再强值转换成浮点数。
01背包？
扩展：
有N种物品（每种物品只有一个）和一个容量为V的背包。第i件物品的占用空间是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路 ：
每种物品仅有一件，只有两种选择：放或不放。 用子问题定义状态：即dp[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
code:
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= W; j++)
{
if(j < w[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
}
}
本题：
将每一张发票当作是一种物品，同样只有两种选择：要或不要，总额度相当于背包容量
注意确保数组够大，1000*100*35
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b)?a:b
int dp[3500000],N[35];
int main()
{
int cot,Val,A,B,C,n,i,j,k,flag;
double val,price;
while(scanf("%lf %d",&val,&cot)!=EOF&&cot)
{
k=0;
char ABC;
memset(dp,0,sizeof(dp));
Val=(int)(val*100);
while(cot--)
{
scanf("%d",&n);
A=0;
B=0;
C=0;
flag=1;
while(n--)
{
scanf(" %c:%lf",&ABC,&price);
j=(int)(price*100);
if(ABC=='A')
A+=j;
else if(ABC=='B')
B+=j;
else if(ABC=='C')
C+=j;
else
{
flag=0;
}
}
if(flag&&A<=60000&&B<=60000&&C<=60000&&A+B+C<=100000)
{
N[k++]=A+B+C;
}
}
for(i=0;i<k;i++)
for(j=Val;j>=N[i];j--)
{
dp[j]=max(dp[j],dp[j-N[i]]+N[i]);
}
printf("%.2lf
",(double)dp[Val]/100.0);
}
}