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

如果求得到offer的最小可能，等价于1-求没有可能的解。

多个概率是相乘。//坑爹的题目，居然有n=0或m=0成立的情况。之前偷懒只判断n等于零WA了好多次

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define mem(a) memset(a,0,sizeof(a)) 8 using namespace std; 9 10 int main()11 {12 int a[10005],n,m;13 while(cin>>n>>m)14 {15 if(n==0&&m==0)break;16 double b[10005],f[10005];17 for(int i=1;i<=m;i++)18 {19 scanf("%d%lf",&a[i],&b[i]);20 b[i]=1-b[i];21 }22 for(int i=0;i<=n;i++)23 f[i]=1;24 for(int i=1;i<=m;i++)25 {26 for(int j=n;j>=a[i];j--)27 {28 f[j]=min(f[j],f[j-a[i]]*b[i]);29 }30 }31 32 printf("%.1lf%%\n",(1.0-f[n])*100);33 }34 return 0;35 }