题目

Description

The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.

For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.

His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.

Input

The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .

Output

For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.

Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.

Sample Input

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

Sample Output

2
4
6

翻译

描述

有志盗贼Roy看了许多美国电影后，发现许多坏蛋被抓的原因是因为他们太贪心。
他决定在退休前在一个利润丰厚的银行干一票大的。
经过几个月，Roy已经从各方面评估了银行的各个方面，他想要做一个稳妥的冒险，然后尽可能抢到更多的钱。
他的妈妈Ola，确定了一个能够容忍的被抓概率。如果被抓的概率大于这个数，那么Roy就不应该去抢劫。

输入

第一行输入T数据个数。
对于每组数据，第一行给一个浮点数P(Roy被抓的概率需要小于这个数)，一个整数N(Roy打算抢劫的银行个数)
接下来的N行，第j给了一个整数Mj(银行钱数)和一个浮点数Pj（被抓的概率）

输出

对于每一组数据，输出一行数。包含其在被抓几率允许范围内所能强到的最大钱数
银行被抢看作独立事件，不互相影响

题解

对于银行i,有钱Mi,被抓几率pi,不被抓的几率为1-p[i]
有抢和不抢两种选择

因此，可以看出来这道题是01背包问题

但是这道题不能用普通的01背包问题思路*(dp[i][j]表示抢劫前i个银行，在被抓几率不大于j时所能抢到最多的钱数)*求解
理由如下：

• 被抓几率是不知道有多少位的小数，不能直接用于下标
• 概率应该相乘，简单的乘除可能会造成重复问题

不能用被抓几率当作背包的下标

发散思维，可以将dp[i][j]看作抢劫前i个银行，在抢劫到j元时，最大的不被抓几率

也即dp[i] = max(dp[i],dp[i - m[i]] * (1-p[i]));

最后在将钱数从大往下筛选，第一个符合dp[i] >= 1-P的就是答案

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 105;

double P,p[maxn];
int N,m[maxn];

int v;

double dp[maxn*maxn];

void ZeroOnePack(int cost,double weight) {
    for(int i = v; i >= cost; i--)
        dp[i] = max(dp[i],dp[i - cost] * weight);
}

void Do() {
    //初始化数据
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    v = 0;

    //数据输入
    scanf("%lf%d",&P,&N);
    for(int i = 1;i <= N;i++) {
        scanf("%d%lf",&m[i],&p[i]);
        v += m[i];
    }

    //dp
    for(int i = 1;i <= N;i++)
        ZeroOnePack(m[i],1-p[i]);

    int ans;
    for(ans = v;ans > 0;ans--) {
        if(dp[ans] >= 1-P)
            break;
    }

    printf("%d\n",ans);
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        Do();
    }
    return 0;
}