题目链接：
HDU 2955 Robberies
题意：
有个robber要去抢银行。抢每个银行会获得金额val[i],同时也会有cost[i]的概率被抓住，问在最大允许被抓住概率为p的情况下可以抢到的最大金额。
分析：
01背包的套路。只不过背包容量换成了被抓住的概率，因为概率是double型的，那就没办法枚举了。
可以倒过来想枚举抢到金额的成功的概率。成功的概率是概率相乘。
//46MS 1532K
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
const int MAX_N=110;
const double eps=1e-6;int T,n,tot,ans,sum;
int val[MAX_N];
double v,cost[MAX_N],dp[MAX_N*MAX_N];int main()
{//freopen("hdu2955in.txt","r",stdin);scanf("%d",&T);while(T--){tot=ans=sum=0;scanf("%lf%d",&v,&n);for(int i=0;i<n;i++){int t;double vv;scanf("%d%lf",&t,&vv);if(vv==0.0) ans+=t;else if(vv<=v+eps){cost[tot]=1-vv;//cost[i]表示成功抢到第i个银行的概率val[tot++]=t;//成功抢到第i个银行所获的价值sum+=t;}}memset(dp,0,sizeof(dp));dp[0]=1;//dp[i]表示抢到总价值为i的概率for(int i=0;i<tot;i++){for(int j=sum;j>=val[i];j--){dp[j]=max(dp[j],dp[j-val[i]]*cost[i]);//printf("i=%d j=%d mp[j]=%d\n",i,j,dp[j]);}}for(int i=sum;i>=0;i--){
//枚举获得价值i的概率if(dp[i]+eps>1-v){
//1-v是不被抓的概率printf("%d\n",i+ans);//最终加上0风险的价值break;}}}return 0;
}