【概率＋01背包】Just another Robbery

系统管理员 2022-05-31 12:45 178阅读 0赞

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

[vjudge题目链接][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;
    }

[vjudge]: https://vjudge.net/problem/LightOJ-1079

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu2955 01背包 Robberies

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

灰太狼/ 2024年02月17日 19:21/ 0 赞/ 42 阅读

相关 01背包

01背包题目描述给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个输入的第一行包

爱被打了一巴掌/ 2022年12月04日 04:27/ 0 赞/ 156 阅读

相关 HDU 2955 Robberies(01背包）

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

墨蓝/ 2022年10月01日 04:54/ 0 赞/ 17 阅读

相关 lightoj 1079 概率计算+01背包

1079 - Just another Robbery <table> <tbody> <tr> <td title="normal judge"><a h

小灰灰/ 2022年07月28日 04:09/ 0 赞/ 140 阅读

相关 HDU 2955-Robberies（01背包变形）

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

青旅半醒/ 2022年07月24日 05:24/ 0 赞/ 126 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 228 阅读

相关 01背包

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。 > > 输入： > 第一行两个整数n，m，分别代表石头的个数

╰半夏微凉°/ 2022年06月08日 09:37/ 0 赞/ 184 阅读

相关【概率＋01背包】Just another Robbery

Think: 1知识点：【概率＋01背包】 2题意：一个人去抢劫银行，当他的被捕概率小于P时才能行动，对于已存在的n个银行，每个银行含有属性w表示含有价值，属性p表示被

系统管理员/ 2022年05月31日 12:45/ 0 赞/ 179 阅读

相关 01背包

01背包 > 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ > > 小Ho现在手上有M张奖券，而奖品区有N

水深无声/ 2022年05月31日 06:29/ 0 赞/ 589 阅读

相关 HDU2955 Robberies————01背包变形

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

系统管理员/ 2022年05月17日 07:35/ 0 赞/ 158 阅读