学步园

又是一道背包题，模式完全一样的，就是稍微注意下格式，然后memset不能对double型的进行初始化。就是练练手。

但是1A还是挺开心的。。。。double注意精度处理问题。

#include <stdio.h>
#include <string.h>
#define maxn 10010
#define eps 1e-12
#define inf 0x3f3f3f3f
double dp[maxn],pro[maxn];
int cost[maxn],n,m;
int sig(double x)
{
    return (x>eps)-(x<-eps);
}
double min(double x,double y)
{
    if(sig(x-y)>0) return y;
    else return x;
}
void init()
{
    for(int i=0;i<=m;i++) dp[i]=1.0000;
}
int main()
{
  //  int n,m;
    while(1)
    {
        scanf("%d%d",&m,&n);
        if(n+m==0) break;
     //   memset(dp,1.0,sizeof(dp));
        init();
        int i,j,k;
        for(i=1;i<=n;i++) scanf("%d%lf",&cost[i],&pro[i]);
      //  for(i=1;i<=n;i++) printf("**%lf",1-pro[i]);printf("\n");
        for(i=1;i<=n;i++)
            {
                for(j=m;j>=cost[i];j--)
            {
          //      printf("**%lf",dp[j-cost[i]]*(1-pro[i]));
                dp[j]=min(dp[j],dp[j-cost[i]]*(1-pro[i]));
            }
         //   printf("\n");
            }
        printf("%.1lf%%\n",(1-dp[m])*100);
    }
    return 0;
}