这个题是0，1背包

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 1e4+10;double dp[maxn];int w[maxn];double v[maxn];int main(){    int n,m,i,j;    while(scanf("%d%d",&n,&m) && n+m)    {        memset(dp, 0, sizeof(dp));        for(i=0; i < m; ++i)        {            scanf("%d %lf",w+i,v+i);            v[i] = 1.0-v[i];        }        for(j=0; j <= n; ++j)        {            dp[j] = 1.0;        }        for(i=0; i
          
           =w[i]; --j) { dp[j] = min(dp[j],dp[j-w[i]]*v[i]); } } printf("%.1f%%\n",(1.0-dp[n])*100); }}