HDOJ 2955 Robberies

   一看题目的时候知道是0/1背包，就是不知道怎么入手，因为我们做的0/1背包是整数，如果用被抓率当容量的话要化成整数，根本无法做。也想过用银行金额来做容量，但是没想到用逃脱率当价值。纠结啊！这里涉及一个概率论的问题，如果用被抓率来算是加法，用逃脱率来说是乘法，因为总的被抓率等于每一次被抓率的总和（或的关系|只要有一次被抓就失败了）。逃脱率的话等于每一次逃脱率的乘积（且的关系|保证每次逃脱才算成功）。

懂了这些0/1背包就没有压力了。

代码：

[cpp]
#include<iostream> 
#include<cmath> 
using namespace std; 
int b[105]; 
double r[105],dp[10005]; 
int main() 
{ 
    int n,t,sum,i,j; 
    double rate,temp; 
    scanf("%d",&t); 
    while( t--){ 
           scanf("%lf%d",&rate,&n); 
           rate=1-rate;    //最低逃跑率  
           sum=0; 
          for( i=1; i<=n; i++){ 
               scanf("%d%lf",&b[i],&temp); 
               r[i]=1-temp; 
               sum+=b[i]; 
          } 
          memset(dp,0,sizeof(dp)); 
          dp[0]=1;   //没偷的时候逃脱率为1；  
          for( i=1; i<=n; i++) 
               for( j=sum; j>=b[i]; j--) 
                    dp[j]=max(dp[j],dp[j-b[i]]*r[i]); 
                     
          for( i=sum; i>=0; i--)   www.zzzyk.com
               if( dp[i]>=rate){  //大于给定逃脱率的最大收益 
                   printf("%d\n",i); 
                   break; 
               } 
            
    } 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：C++设计一个类不能偷懒的地方
下一个：C++ 静态变量之为什么只初始化一次