【概率＋01背包】Just another Robbery-蒲公英云

【概率＋01背包】Just another Robbery

Think:
1知识点：【概率＋01背包】
2题意：一个人去抢劫银行，当他的被捕概率小于P时才能行动，对于已存在的n个银行，每个银行含有属性w表示含有价值，属性p表示被捕概率，每个银行的被捕概率为独立的。询问在被捕概率小于P的前提，可以抢劫的最大价值。
3思路：
3.1：[将被捕概率转换为安全概率，即将被捕概率小于P的限制条件转换为安全概率不小于1-P] + [01背包体积：价值]

vjudge题目链接

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
    int w;
    double p;
}rec[104];
double dp[10414];
int main(){
    int k = 1, T, V, n, i, j;
    double P;
    scanf("%d", &T);
    while(T--){
        scanf("%lf %d", &P, &n);
        P = 1 - P, V = 0;
        for(i = 0; i < n; i++){
            scanf("%d %lf", &rec[i].w, &rec[i].p);
            rec[i].p = 1 - rec[i].p, V += rec[i].w;
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(i = 0; i < n; i++){
            for(j = V; j >= rec[i].w; j--){
                dp[j] = max(dp[j], dp[j-rec[i].w]*rec[i].p);
            }
        }
        for(i = V; i >= 0; i--){
            if(dp[i] >= P){
                printf("Case %d: %d\n", k++, i);
                break;
            }
        }
    }
    return 0;
}