01背包。将最大金额作为容量v。概率做乘法。

1 #include 
     
       2 #include 
      
        3  4 #define mymax(a, b) (a>b) ? a:b 5  6 float dp[10005]; 7 int mon[105]; 8 float fs[105]; 9 10 int main() {11     int case_n;12     float ff, f;13     int m, v;14     int i, j;15 16     scanf("%d", &case_n);17 18     while (case_n--) {19         scanf("%f %d", &ff, &m);20         v = 0;21         for (i=1; i<=m; ++i) {22             scanf("%d %f", &mon[i], &fs[i]);23             fs[i] = 1 - fs[i];24             v += mon[i];25         }26         ff = 1 - ff;27         memset(dp, 0, sizeof(dp));28         dp[0] = 1;29         for (i=1; i<=m; ++i) {30             for (j=v; j>=mon[i]; --j) {31                 dp[j] = mymax(dp[j], dp[j-mon[i]]*fs[i]);32             }33             /*34             for (j=0; j<=v; ++j) {35                 printf("%f ", dp[j]);36             }37             printf("\n");38             */39         }40         for (i=v; i>0; --i)41             if (dp[i] >= ff)42                 break;43         printf("%d\n", i);44     }45 46     return 0;47 }