1 . Robberies (hdu 2955)，robberieshdu2955

1 . Robberies (hdu 2955)，robberieshdu2955

題目鏈接   http://acm.hdu.edu.cn/showproblem.php?pid=2955

題意 小偷有個總的逃跑概率，每個銀行有一個錢數和逃跑概率，問在總的逃跑概率下能最多獲得多少錢？

思路：開始有0-1背包寫，把概率擴大100倍，wa了，重改思路。把總價格當容量，被抓的概率為價值 在被抓的概率大於總概率時的容量為多少

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
using namespace std;
#define N 10100
#define ll long long
#define INF 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof(a));
vector<vector<int> >Q;
double dp[N],w[N];
int v[N];
int main()
{
int n,t,sum;
double p;
scanf("%d",&t);
while(t--)
{
scanf("%lf %d",&p,&n);
sum=0;
for(int i=1; i<=n; i++)
{
scanf("%d %lf",&v[i],&w[i]);
sum+=v[i];
}
met(dp,0);
dp[0]=1;
for(int i=1; i<=n; i++)
{
for(int j=sum; j>=v[i]; j--)
{
dp[j]=max(dp[j],dp[j-v[i]]*(1-w[i]));
//printf("%d %d\n",j,dp[j]);
}

}
p=1-p;
for(int i=sum;i>=0;i--)
{
if(dp[i]>=p)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}