本文主要是介绍01背包dp变形--Robberies，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个强盗要抢劫银行又不想被抓到，所以要进行概率分析求他在不被抓的情况下能抢最多的钱。他给定T（样例个数），N（要抢的银行的个数），P（被抓的概率要小于P）Mj（强盗能抢第j个银行Mj元钱），Pj（强盗抢第j个银行被抓的概率为Pj）。
思路：被抓的概率不好直接求出来，但可以直接求出不被抓的概率，则有状态转移方程dp[j] = max(dp[j], dp[j-b[i].money]*b[i].p)表示抢到j元钱被抓的最大的概率是多少。然后逆序遍历第一个小于P的dp的下标就是答案。
PS：数组的下标表示的是可以抢到的钱数，所以不能按100来开数组。。。。。。。。（T到吐血）
代码：
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)using namespace std;
typedef long long ll;
const int maxn = 10000;
double dp[maxn];
struct Bank
{int money;double p;
} bb[maxn];int main()
{ios::sync_with_stdio(false);int T,n;double p;cin>>T;while(T--){int sum = 0;cin>>p>>n;for(int i = 0; i<n; i++){cin>>bb[i].money>>bb[i].p;sum += bb[i].money;}memset(dp,0,sizeof(dp));dp[0] = 1;for(int i = 0; i<n; i++){for(int j=sum; j>=bb[i].money; j--){dp[j] = max(dp[j], dp[j-bb[i].money]*(1.0 - bb[i].p));}}int ans = 0;for(int i = sum; i>=0; i--){if(1-dp[i]<=p){ans = i;break;}}cout<<ans<<endl;}return 0;
}
这篇关于01背包dp变形--Robberies的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
