0-1背包问题，总容量设为从所有银行获益的总和，价值为不被抓捕的概率。

 

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 const int maxn = 1e4 + 10; 8 const int maxm = 1e2 + 10; 9 10 int v[maxm], n;11 double dp[maxn], p[maxm], P;12 13 int main(){14     int T;15     scanf("%d", &T);16     while(T--){17         scanf("%lf%d", &P, &n);18         int sum = 0;19         for(int i = 0; i < n; i++) scanf("%d%lf", &v[i], &p[i]), sum += v[i];20         memset(dp, 0, sizeof dp);21         dp[0] = 1;22         for(int j = 0; j < n; j++){23             for(int i = sum; i >= v[j]; i--){24                 dp[i] = max(dp[i], dp[i - v[j]] * (1 - p[j]));25             }26         }27         for(int i = sum; i >= 0; i--) if(dp[i] >= 1 - P){28             printf("%d\n", i);29             break;30         }31     }32     return 0;33 }