题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1864
题目中给的数据是浮点型，背包问题处理的是整形数据，所以先*100将其转化为整形。
题目的输入数据比较复杂，我门需要先选出符合要求的发票，然后就是在符合要求的发票中选取一些发票，使得总金额最接近给的金额。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[3000005]; int a[3000005]; int main() { int n; double q; while(scanf("%lf %d",&q,&n) && n != 0) { int m; int num = 0; int maxx=(int)(q*100); for(int i = 0;i<n;i++) { scanf("%d",&m); char tc; double pi; double va,vb,vc; va =vb =vc = 0; int biaoji=1; for(int j = 0;j<m;j++) { scanf(" %c:%lf",&tc,&pi); if(tc == ‘A‘) { va = va + pi; }else if(tc == ‘B‘) { vb = vb + pi; }else if(tc == ‘C‘) { vc = vc + pi; }else { biaoji = 0; } } if(biaoji==1 && va<=600 && vb<=600 && vc<=600 && va+vb+vc<=1000) { a[num] = (int)((va+vb+vc)*100); num++; } } memset(dp,0,sizeof(dp)); for(int i = 0;i<num;i++) { for(int j = maxx;j>=a[i];j--) { dp[j] = max(dp[j],dp[j-a[i]]+a[i]); } } printf("%.2lf\n",(dp[maxx])/100.0); } return 0; }
原文：https://www.cnblogs.com/hdyss/p/10853563.html