撰写- HDU1864-最大报销额
- 题意
- 现有一笔经费可以报销一定额度的发票。
- 允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类）
- 要求
- 每张发票的总额不得超过1000元，
- 每张发票上，单项物品的价值不得超过600元
- 在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。
- 题解
- 先筛选再背包
- 但是两个问题，一个是精度问题，另一个是浮点数不可以做数组下标
- 而背包问题却需要用花费作为背包的容量
- 注意到题目中给出的数据都是两位小数
- 那么我们就先将所有数*100，输出时/100.0即可
- 代码
-
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<vector> #include<map> #include<stack> #include<queue> #include<cmath> #include<fstream> #include<algorithm> using namespace std; #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) //#define CLR(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ull; const double eps=1e-6; const int INF = 0x3f3f3f3f; const int maxn=3e6+10; int t[50]; int v[50]; int dp[maxn]; int cnt; int main(){ double m; int n; while(scanf("%lf%d", &m,&n)!=EOF&&n!=0){ cnt=0; while(n--){ int q; int sum=0; double num; scanf("%d", &q); rep(i,0,25){ t[i]=0; } rep(i,1,q){ getchar(); char tmp=getchar(); int x=tmp-'A'; tmp=getchar(); scanf("%lf", &num); int Num=int(num*100); t[x]+=Num; sum+=Num; } int flag=1; if(sum-100000>0){ flag=0; continue; } rep(i,0,2){ if(t[i]-60000>0){ flag=0; break; } } rep(i,3,25){ if(t[i]>0){ flag=0; break; } } if(flag){ v[++cnt]=sum; //cout<<v[cnt]<<endl; } } int M = int(m*100); M=min(M,maxn-10); rep(i,0,M){ dp[i]=0; } for(int i=1;i<=cnt;i++){ for(int j=M;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+v[i]); } } printf("%d.", dp[M]/100); if(dp[M]%100<10)printf("0"); printf("%d\n",dp[M]%100); } return 0; }
-
- 题意
- HDU-1293-I NEED A OFFER
- 题意
- n所学校，每个学校的申请费用为ai，报上的的可能性为bi（不同学校报上的可能性独立）
- 有m元，问你申请上学校的概率最多是多少
- 题解
- 显然，背包问题，只要（1-不可能）即可
- 而这里的费用都是整数，所以可以直接写出背包
- 因为我们要确保f[m]能得到最终答案，故将dp[]初始化为1.0，
- 跑0-1背包，f[j] = min(f[j], f[j-v[i]]*(1-p[i]))
- 代码
-
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<vector> #include<map> #include<stack> #include<queue> #include<cmath> #include<fstream> #include<algorithm> using namespace std; #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) //#define CLR(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ull; const double eps=1e-6; const int INF = 0x3f3f3f3f; const int maxn=3e6+10; double f[10100]; int v[10100]; double w[10100]; int main(){ int n,m; while(scanf("%d%d", &m,&n)!=EOF){ if(n==0&&m==0)break; rep(i,1,n){ scanf("%d%lf", &v[i], &w[i]); } rep(i,0,m){ f[i]=1.0; } rep(i,1,n){ for(int j=m;j>=v[i];j--){ f[j]=min(f[j],f[j-v[i]]*(1-w[i])); } } printf("%.1f%%\n", 100-f[m]*100); } return 0; }
-
- 题意
- HDU2995-Robberies
- 题意
- n座银行，每座有ai元（整数），抢银行被抓的概率为pi（浮点数）（相互独立）
- 给出一个概率P
- 在被抓的概率小于P的情况下，尽可能拿到更多的钱
- 题解
- 显然，还是背包问题
- 但是这里有个问题，我们需要得到的是钱数，那么概率就需要作为数组下标，这样显然是行不通的
- 所以我们反过来想，仍将钱数当作背包第二维，计算被抓的概率
- 最后从后向前扫一遍，扫到概率小于P则输出
- 代码
-
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<vector> #include<map> #include<stack> #include<queue> #include<cmath> #include<fstream> #include<algorithm> using namespace std; #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) #define CLR(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ull; const double eps=1e-6; const int INF = 0x3f3f3f3f; const int maxn=2e5+10; int w[maxn]; double v[maxn]; double dp[maxn]; int main() { int t; scanf("%d", &t); while(t--){ int n; int sum=0; double P; scanf("%lf%d", &P,&n); rep(i,1,n)scanf("%d%lf", &w[i],&v[i]),sum+=w[i]; rep(i,1,sum)dp[i]=0.0; dp[0]=1.0; rep(i,1,n){ per(j,w[i],sum){ dp[j] = max(dp[j],dp[j-w[i]]*(1.0-v[i])); } } per(i,0,sum){ if(dp[i]>=1.0-P){ printf("%d\n", i); break; } } } return 0; }
-
- 题意
