hdu 2955 Robberies（01背包）

題目意思：

01背包的簡單變異。。

dp[i]表示偷取i元不被抓的概率。。。

dp[j]=max(dp[j]，dp[j-mm[i]]*(1-pp[i])）

[csharp] 
#include"stdio.h" 
#include"string.h" 
#define max(x,y) x>y?x:y; 
double dp[10001]; 
int main() 
{ 
    int sum,i,j,mm[101],t,n; 
    double p,pp[101]; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%lf%d",&p,&n); 
        sum=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%lf",&mm[i],&pp[i]); 
            sum+=mm[i]; 
        } 
        memset(dp,0,sizeof(dp)); 
        dp[0]=1; 
        for(i=0;i<n;i++) 
        { 
            for(j=sum;j>=mm[i];j--) 
                dp[j]=max(dp[j],dp[j-mm[i]]*(1-pp[i])); 
        } 
        for(i=sum;i>=0;i--) 
        { 
            if(dp[i]>=(1-p)) 
            { 
                printf("%d\n",i);break; 
            } 
        } 
    } 
    return 0; 
}