这的确是一个背包问题，但是他又有不一样的地方就在于对于实型的处理应该怎么做。
现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（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
首先先将一种积累的方法，就是先知道所有可以可以报销的金额的总和，然后现在的背包就变成了放弃几个数而不再是要拿几个数，但是原理是一样的。
他有两类主要函数：
一：
double temp=0;
int v[50]={0};
memset(v, 0, sizeof(v));
while(sum>Q)
{
int now_i=0;
for(int i=0; i<cnt && !v[i]; i++)
{
if(temp<sum-a[i])
{
temp=sum-a[i];
now_i=i;
}
}
sum=temp;
v[now_i]=1;
}
二：
while(whole>Q)
{
double temp=0;
for(int i=0; i<cnt; i++)
{
temp=temp>(whole-sum[i])?(temp):(whole-sum[i]);
}
whole=temp;
}
亦或者是：
int v[50]={0};
memset(v, 0, sizeof(v));
while(sum>Q)
{
double temp=0;
int now_i=0;
for(int i=0; i<cnt && !v[i]; i++)
{
if(temp<sum-a[i])
{
temp=sum-a[i];
now_i=i;
}
}
sum=temp;
v[now_i]=1;
}
这几类做法都是可以的，然而我接下来要写一种背包，就是将dp[i]中的i记录为背包中剩余的物品，dp[0]为满背包情况，每次+1都会丢弃一种最轻的物品，然后寻找所有符合条件中，最大的那个量即可。
主要代码：
dp[0]=sum; //接下来每+1表示扔了一个数
for(int i=0; i<cnt; i++)
{
for(int j=N; j>=1; j--)
{
if(dp[j-1]) dp[j]=dp[j]>(dp[j-1]-a[i])?dp[j]:(dp[j-1]-a[i]);
if(dp[j]<=Q && ans<dp[j])
{
ans=dp[j];
}
}
}
if(dp[0]<=Q)
{
ans=dp[0];
}
因为主要代码部分相同且可以相互改换（但要注意我的定义的变量名要改）所以我发思路不同的两份的完整代码：
代码一：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double Q;
int N;
double money[30];
double sum[30];
double ans[30005];
int main()
{
while(scanf("%lf %d",&Q,&N)&&N)
{
double whole=0; //记录所有可以抵消的发票总价，通过一一排掉小的，得到最接近Q且小于等于Q大的答案。
int cnt=0;
memset(ans, 0, sizeof(ans));
for(int i=0; i<N; i++)
{
int n;
scanf("%d",&n);
memset(money, 0, sizeof(money));
bool flag=true;
for(int j=0; j<n; j++)
{
char ss[2];
double mon;
getchar();
scanf("%c%c",&ss[0],&ss[1]);
scanf("%lf",&mon);
money[ss[0]-'A']+=mon;
if(ss[0]-'A'>=3)flag=false;
}
if(money[0]<=600&&money[1]<=600&&money[2]<=600&&(money[0]+money[1]+money[2])<=1000&&flag)
{
sum[cnt++]=money[0]+money[1]+money[2];
whole+=money[0]+money[1]+money[2];
}
}
while(whole>Q)
{
double temp=0;
for(int i=0; i<cnt; i++)
{
temp=temp>(whole-sum[i])?(temp):(whole-sum[i]);
}
whole=temp;
}
printf("%.2lf\n",whole);
}
return 0;
}
代码二：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MT(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
double mon[30];
double a[50];
double dp[50];
double Q;
int N;
int main()
{
while(scanf("%lf %d",&Q,&N)!=EOF)
{
if(N==0)break;
double sum=0;
double ans=0;
int cnt=0;
int n;
MT(a, 0);
MT(dp, 0);
for(int i=0; i<N; i++) //发票数量
{
bool flag=false;
for(int i=0; i<3; i++) mon[i]=(double)0;
double temp;
scanf("%d",&n);
char s[2];
for(int j=0; j<n; j++)
{
getchar();
scanf("%c%c",&s[0],&s[1]);
scanf("%lf",&temp);
if(s[0]-'A'>2)flag=true;
mon[s[0]-'A']+=temp;
}
if(!flag && mon[0]<=600 && mon[1]<=600 && mon[2]<=600 && mon[0]+mon[1]+mon[2]<=1000)
{
a[cnt++]=mon[0]+mon[1]+mon[2];
sum+=a[cnt-1];
}
}
dp[0]=sum; //接下来每+1表示扔了一个数
for(int i=0; i<cnt; i++)
{
for(int j=N; j>=1; j--)
{
if(dp[j-1]) dp[j]=dp[j]>(dp[j-1]-a[i])?dp[j]:(dp[j-1]-a[i]);
if(dp[j]<=Q && ans<dp[j])
{
ans=dp[j];
}
}
}
if(dp[0]<=Q)
{
ans=dp[0];
}
printf("%.2lf\n",ans);
}
return 0;
}
