hdu 2955 Robberies(0/1背包)

点击打开链接hdu 2955

思路: 0/1背包
分析:
1 按照题目的意思我们很容易知道这就是一个0/1背包问题，如果我们把概率当作是背包的容量，那么我们遇到一个问题就是浮点数的dp，因为题目没有告诉我们小数点具体几位，那么我们就不能够通过乘上10^n来转化为整数，所以我们应该考虑换种思想
2 按照正常的思路是dp[i][j]表示前i个物品放入概率为j的最大价值，那么我们这边把价值当成背包来看的话我们设dp[i][j]表示前i个物品放入金钱为j的最小被抓概率(因为题目不好求最小概率我们可以认为是最大的不被抓概率)
3 最后去从大到小枚举找到一个被抓的概率小于p即可

代码:

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

const int N = 110;
const int MAXN = 10010;

double p;
int n , sum , v[N] , minV;
double dp[MAXN] , w[N];

int solve(){
    memset(dp , 0 , sizeof(dp));
    dp[0] = 1;//  注意当什么钱都没有抢的时候不被抓的概率为1
    for(int i = 1 ; i <= n ; i++)
        for(int j = sum ; j >= v[i] ; j--)
            dp[j] = max(dp[j] , dp[j-v[i]]*(1.0-w[i]));// 这里求不被抓就是每一次都不被抓即相乘
    for(int j = sum ; j >= minV ; j--)
        if(1.0-dp[j] <= p)
            return j;
    return 0;
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
         scanf("%lf%d" , &p , &n); 
         sum = 0;
         minV = 1<<30;
         for(int i = 1 ; i <= n ; i++){
             scanf("%d%lf" , &v[i] , &w[i]);
             sum += v[i];
             minV = min(minV , v[i]);
         }
         printf("%d\n" , solve());
    }
    return 0;
}