Robberies
题目注意的是，概率的精度问题，不是只有两位小数。。有很多位，所以要转换思路。
我也是看了网上的解题报告后，懂的。
不同之处：
一般的理解，背包容量应为概率1。转化思路，背包容量为银行总的钱数。
改为在总钱数一定的情况下，通过少抢点钱来增加自己安全的逃跑概率，在大于等于给定逃跑概率时求解所能获得的最大钱数。
#include <iostream>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
double escape[102],secrity[10001];
int money[102];
int n;
double p;
void knapsack(int n,int sum)
{
secrity[0]=1.0;
for(int i=1;i<=n;i++)
for(int j=sum;j>=money[i];j--)
{
secrity[j]=max(secrity[j],secrity[j-money[i]]*escape[i]);//安全概率是相乘的关系。只有都安全才是真正的安全。
}
for(int i=sum;i>=0;i--)//i表示的所抢的总钱数。钱数与安全概率一定是成反比的。i=sum时安全概率最低
if(secrity[i]>=1-p)//随着所抢钱数i的减小，安全概率递增。一旦满足大于(1-p)。立即停止，此时i为最大钱数
{
cout<<i<<endl;
break;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>p>>n;
int sum=0;
memset(secrity,0,sizeof(secrity));
for(int i=1;i<=n;i++)
{
cin>>money[i]>>escape[i];
escape[i]=1-escape[i];
sum+=money[i];
}
knapsack(n,sum);
}
return 0;
}