本文共 900 字，大约阅读时间需要 3 分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2955

题意：小偷想偷银行的钱给出小偷被抓的概率和n个银行，接下来给你n行数据 每行给出分别是银行的钱数和小偷被抓的概率

求在不大于小偷被抓的概率下能得到银行的钱数是多少；

状态转移：

把钱数当成体积               不被抓概率当成价值

状态方程：dp[j] = max(dp[j],dp[j-v[i]] *w[i];

#include 
   
    #include 
    
     #include 
     
      using namespace std;double dp[10005];int n;double p;double w[105];int v[105];void DP(int V){    memset(dp,0,sizeof(dp));    dp[0] = 1.0;    for(int i = 0;i < n;i++)    {        for(int j = V;j >= v[i];j--)        {            dp[j] = max(dp[j],dp[j-v[i]]*(1-w[i]));        }    }    for(int i = V;;i--)    {        if(dp[i] > 1 - p)        {            printf("%d\n",i);            break;        }    }}int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%lf%d",&p,&n);        int sum = 0;        for(int i = 0;i < n;i++)        {            scanf("%d%lf",&v[i],&w[i]);            sum += v[i];        }        DP(sum);    }}
     
    
   

转载地址：http://cysgi.baihongyu.com/