HDU2955 01 背包 Robberies

一、题目内容

【题目描述】

Roy想要抢劫银行，每家银行都有一定的金额和被抓到的概率，知道Roy被抓的最大概率P，求Roy在不被抓的情况下，最多抢劫多少钱。

【输入格式】

第一行输入给出T，即案例数。
对于每个场景，第一行输入给出浮点数P，Roy需要低于的概率，以及整数N，即他计划的银行数。
然后接下来N行，其中第j行给出整数Mj和浮点数Pj . 表示 Bank j包含Mj百万，并且被抓住它的概率是Pj。

【输出格式】

对于每个测试用例，输出一个他可以获得的最大数百万行，而被捕获的概率小于限制集.
0 <T <= 1000.0 <= P <= 1.00 <N <= 1000 <Mj <= 1000.0 <= Pj <= 1.0
银行如果被抢劫就会破产，你可以认为所有概率都是独立的。

【输入样例】

3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05

【输出样例】

2
4
6

【测试网站】

HDU2955

二、题目分析

到达性dp问题。
状态转移方程为 dp[j] = max(dp[j],dp[j-v[i]] * (1-p[i])); dp[i] 表示能抢到i个百万不被抓到的最大概率。
套用01背包模板，把银行里的总钱数当作总容量，概率当作价值 ，最后再根据概率判断其能不能到达该钱数。
被抓到的最小概率 = 1-不被抓到的最大概率

三、代码示例

#include <bits/stdc++.h>

using namespace std;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
int T;
int n,k;
double P;
double p[maxn];
int v[maxn];
double dp[10005]; //dp数组，dp[i] 代表能抢到i个百万不被抓到的最大概率

int main()
{
   int T;
   scanf("%d",&T);
   while(T--)
   {
    scanf("%lf%d",&P,&n);
    int sum = 0;
    for(int i = 0; i < n; i++)  scanf("%d%lf",&v[i],&p[i]), sum += v[i]; //统计总钱数
    for(int i = 0; i <= sum; i++) dp[i] = 0; //初始化dp 数组
    dp[0] = 1;  //抢到0个百万的概率总是为1
    for(int i = 0; i < n; i++)
      for(int j = sum; j-v[i] >= 0; j--)
         dp[j] = max(dp[j],dp[j-v[i]] * (1-p[i]));  //状态转移
    int ans;
    for(int i = sum; i >= 0; i--)
            if(1-dp[i] <= P)  //被抓到的最小概率 = 1-不被抓到的最大概率
              {ans = i;break;}
    printf("%d\n",ans);
   }
   return 0;
}