Robberies

#include<stdio.h>
double max(double a,double b)
{
    return a>b?a:b;
}
int main()
{
    int t,n,M[110],i,j,sum;
    double p,P[110],dp[10010];   //dp为背包最大容量
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        scanf("%lf%d",&p,&n);
        dp[0]=1;              //当抢到的钱为零时，不被抓的概率为1
        for(i=0; i<n; i++)
        {
            scanf("%d%lf",&M[i],&P[i]);
            sum+=M[i];
        }
        for(i=1; i<=sum; i++)     //需将除dp[0]以外的所有元素初始化为零，因为状态转移方程要比较大小再赋值，见图。之前错在此处。
            dp[i]=0.0;
        for(i=0; i<n; i++)              //此循环为遍历银行
            for(j=sum; j>=M[i]; j--)     //此处不易理解。假设银行（1，0.02）（2，0.03)(3,0.05)  此循环大概功能：dp[6]=dp[3]*P[3],dp[3]=dp[1]*P[2].
                dp[j]=max(dp[j],dp[j-M[i]]*(1-P[i]));    //状态转移方程
        for(i=sum; i>=0; i--)
            if(dp[i]>=(1.0-p))
            {
                printf("%d\n",i);
                break;
            }
    }
    return 0;
}