hdoj-acm-step-3.3.5

hdoj acm step 3.3.5 Robberies (01背包)

转载自：源地址
思路：
这里的最大被抓概率，正面求解是不好求的，而且是浮点数，不能当做背包的维数，所以只能做背包的价值，正面求解最小被抓概率是不好求的，有很多情况，所以应该反面来求解，求解最大的不被抓的概率，这样的话就是直接连乘了，p = (1-p1)(1-p2)(1-p3)（其中p为最大不被抓概率，p1,p2,p3分别是在银行123被抓的概率）

所以这里应该把能抢到的钱作为背包，概率作为价值，每次求解当前抢到的钱的最大不被抓概率。

dp[j] = max(dp[j],dp[j-Bag[i].v]*(1-Bag[i].p))(dp[j]表示在抢到的钱为j的时候最大的不被抓的概率);

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define maxn 10005
double dp[maxn];
int v[maxn];
double w[maxn];

int main()
{
    int t;
    cin >> t;
    while(t--) {
        int n, i, j, sum = 0;
        double m;
        cin >> m >> n;
        //memset(v, 0, sizeof(v));
        //memset(w, 0, sizeof(w));

        for(i = 0; i < n; i++) {cin >> v[i] >> w[i]; sum += v[i]; }

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;

        for(i = 0;i < n;i++) {
            for(j = sum;j >= v[i];j--) {
                dp[j] = max(dp[j], dp[j - v[i]] * (1 - w[i]));
            }
        }

        for(j = sum; j >= 0; j--) {
            //if(dp[j] > 1 - m)
                //cout << "result: "<< j << " " << dp[j] <<endl;
            if(dp[j] - 1 + m > 0.0) {
                cout << j << endl;
                break;
            }
        }
    }
    return 0;
}