beibao

#include <stdio.h>
#include <string.h>
double MAX(double a,double b)
{   
 return a>b?a:b;
}
int main()
{ 
 double f[10000],w[1010];
 int i,j,m,n,c[1010];
    while (scanf("%d%d",&n,&m)!=EOF&&(m!=0&&n!=0))  
 {
  for (i=0;i<m;i++)
            scanf("%d%lf",&c[i],&w[i]);
        memset(f,0,sizeof(f));
  for (i=0;i<m;i++)
   for (j=n;j>=c[i];j--)
                f[j]=MAX(f[j],(1-(1-f[j-c[i]])*(1-w[i])));
            printf("%.1lf%%\n",f[n]*100);
    }
    return 0;
}

Input

Output

Sample Input

10 3
4 0.1
4 0.2
5 0.3
0 0

Sample Output

44.0%

Hint

Author

beibao,布布扣,bubuko.com

beibao

原文：http://www.cnblogs.com/luzhongshan/p/3891846.html