一看題目的時候知道是0/1背包，就是不知道怎麼入手，因為我們做的0/1背包是整數，如果用被抓率當容量的話要化成整數，根本無法做。也想過用銀行金額來做容量，但是沒想到用逃脫率當價值。糾結啊！這裡涉及一個概率論的問題，如果用被抓率來算是加法，用逃脫率來說是乘法，因為總的被抓率等於每一次被抓率的總和（或的關系|只要有一次被抓就失敗了）。逃脫率的話等於每一次逃脫率的乘積（且的關系|保證每次逃脫才算成功）。
懂了這些0/1背包就沒有壓力了。
代碼：
[cpp]
#include<iostream>
#include<cmath>
using namespace std;
int b[105];
double r[105],dp[10005];
int main()
{
int n,t,sum,i,j;
double rate,temp;
scanf("%d",&t);
while( t--){
scanf("%lf%d",&rate,&n);
rate=1-rate; //最低逃跑率
sum=0;
for( i=1; i<=n; i++){
scanf("%d%lf",&b[i],&temp);
r[i]=1-temp;
sum+=b[i];
}
memset(dp,0,sizeof(dp));
dp[0]=1; //沒偷的時候逃脫率為1；
for( i=1; i<=n; i++)
for( j=sum; j>=b[i]; j--)
dp[j]=max(dp[j],dp[j-b[i]]*r[i]);
for( i=sum; i>=0; i--) www.2cto.com
if( dp[i]>=rate){ //大於給定逃脫率的最大收益
printf("%d\n",i);
break;
}
}
return 0;
}
