Robberies

  依然是01背包，但这次的有点特殊。特殊之处在于，背包的总体积是可以获得的钱的最大值( 如果是以概率为背包也不能枚举啊23333 )，然后用动态规划求得获得该钱数被抓的最大概率( 如果在最大概率的情况下都不会被抓，那就肯定不会被抓 )。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
int m[105];
double p[105];
double dp[10000];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {    
        mst(dp,0);mst(m,0);mst(p,0);
        dp[0]=1.0;
        int n;double ptot;
        cin>>ptot>>n;
        int sum=0;
        for(int i=0;i<n;i++)
        {    
            cin>>m[i]>>p[i];
            sum+=m[i];
        }
        for(int i=0;i<n;i++)
            for(int j=sum;j>=m[i];j--)
                dp[j]=max(dp[j],dp[j-m[i]]*(1.0-p[i]));
      //这里先求不会被抓的概率然后用1减去这个概率，就是被抓的概率(高中数学)
        for(int j=sum;j>=0;j--)
        {    
            double ans=1.0-dp[j];
            if(ptot-ans>1e-9){
                cout<<j<<endl;
                break;
            }        
        }
    }
    return 0;
}