题目：https://vjudge.z180.cn/problem/LightOJ-1079
题意：首先给你一个最大被抓的概率p和n家银行，每一家银行有一个金钱wi和被抓概率pi，问在不超过p的前提下，最多能够获得多少金钱。
题解：01背包，把金钱当背包容量，1-pi当价值，然后求价值最大就好，再从大到小扫一遍背包，找到第一个大于1-p的那个背包容量，就是答案，，，pi是被抓概率，转化为1-pi就是不被抓概率，那么求在当前背包容量下不被抓概率的最大值。
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <functional> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#include <unordered_map> //#include <unordered_set> //#include <bits/stdc++.h> //#define int long long #define pb push_back #define PII pair<int, int> #define mpr make_pair #define ms(a, b) memset((a), (b), sizeof(a)) #define x first #define y second typedef long long ll; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 1e7 + 7; using namespace std; double f[N], v[N]; int w[N]; // signed main(){ int main(int argc, char const *argv[]) { int T; // printf("%.10lf\n",-1e8+(-0.02)); int Case = 0; scanf("%d", &T); while (T--) { int n; double p; for (int i = 1; i <= 10000; i++) f[i] = 0; //总的金钱和不超过10000 scanf("%lf%d", &p, &n); p = 1 - p; //求不被抓的概率 for (int i = 1; i <= n; i++) { int val; double pi; scanf("%d%lf", &val, &pi); w[i] = val, v[i] = 1 - pi; //存不被抓的概率，用w[i]当体积 } f[0] = 1; // dp入口 for (int i = 1; i <= n; i++) { for (int j = 10000; j >= w[i]; j--) { //找那个小容量的不被抓的概率，再乘以我这个不被抓的概率 //就是到这一步不被抓的概率 f[j] = max(f[j], (f[j - w[i]]) * v[i]); } } int pos = 0; for ( int i = 10000; i >= 1; i--) { //从最大开始找一个不被抓的概率大于我的p(这里的p已经处理为不被抓的概率) if ((f[i]) >= p) { pos = i; //记录位置输出 break; } } printf("Case %d: ", ++Case); printf("%d\n", pos); } return 0; }
原文：https://www.cnblogs.com/Are-you-ready/p/14865375.html
