题意：Roy想要抢劫银行，每家银行多有一定的金额和被抓到的概率，知道Roy被抓的最大概率P，求Roy在被抓的情况下，抢劫最多。 思路：由于概率不是整数，所以不能以概率为背包容量，我们以金额为背包容量，dp[i]意义为当抢劫金额为i是被抓概率最小（我们将概率p转换为1-p，求其最大）；
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<queue> #include<cmath> #include<stack> #include<vector> #include<cstdio> #define MAXN 33000 #define INF 0x3f3f3f3f #define lmid l,m,rt<<1 #define rmid m+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 #define Mod 1000000007 #define i64 __int64 using namespace std; int x[105]; double num[105]; double dp[10005]; int main() { int t; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); int n; double m; scanf("%lf%d",&m,&n); m=1.0-m; int sum=0; for(int i=1;i<=n;i++) { scanf("%d%lf",&x[i],&num[i]); sum+=x[i]; num[i]=1.0-num[i]; } dp[0]=1.0; for(int i=1;i<=n;i++) for(int j=sum;j>=x[i];j--) { dp[j]=max(dp[j],dp[j-x[i]]*num[i]); } int ans; for(int i=sum;i>=0;i--) { //cout<<dp[i]<<" "<<i<<endl; if(dp[i]-m>=1e-8) { ans=i; break; } } cout<<ans<<endl; } return 0; }