【01背包变形】Robberies HDU 2955

http://acm.hdu.edu.cn/showproblem.php?pid=2955

【题意】

有一个强盗要去几个银行偷盗，他既想多抢点钱，又想尽量不被抓到。已知各个银行

的金钱数和被抓的概率，以及强盗能容忍的最大被抓概率。求他最多能偷到多少钱？

【思路】

01背包：每个物品代价是每个银行钱的数目，物品的价值是在该银行不被抓的概率（1-被抓概率），背包容量是所有银行钱的总和。01背包求dp[i]表示获得i的钱不被抓的最大概率。最后从大到小枚举出 dp[i]>=(1-P)这个i就是答案了。

【AC】

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn=1e2+;

 double P;

 int n;

 int w[maxn];

 double p[maxn];

 double dp[];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%lf%d",&P,&n);

         int sum=;

         for(int i=;i<=n;i++)

         {

             scanf("%d%lf",&w[i],&p[i]);

             sum+=w[i];

         }

         P=-P;

         for(int i=;i<=sum;i++) dp[i]=;

         dp[]=;

         for(int i=;i<=n;i++)

         {

             for(int j=sum;j>=w[i];j--)

             {

                 dp[j]=max(dp[j],dp[j-w[i]]*(-p[i]));

             }

         }

         for(int i=sum;i>=;i--)

         {

             if(dp[i]>P)

             {

                 printf("%d\n",i);

                 break;

             }

         }

     }

     return ;

 }

01背包变形

巴特西

【01背包变形】Robberies HDU 2955

最新文章

热门文章