0-1背包
//状态转移方程为:dp[i]=max(dp[i],dp[i-m]*(1-op));
#include<stdio.h> #include<string.h> int main() { int i,j,v[120],sum,n,t; double w[120],dp[10010],op; scanf("%d",&t); while(t--) { sum=0; scanf("%lf%d",&op,&n); op=1-op; for(i=0;i<n;i++) { scanf("%d%lf",&v[i],&w[i]); w[i]=1-w[i]; sum=sum+v[i]; } dp[0]=1; for(i=1;i<=sum;i++) dp[i]=0; for(i=0;i<n;i++) { for(j=sum;j>=v[i];j--) if(dp[j-v[i]]*w[i]>dp[j]) dp[j]=dp[j-v[i]]*w[i]; } for(i=sum;i>=0;i--) { if(dp[i]>=op) { printf("%d\n",i); break; } } } return 0; }