Robberies

題意：題目的大概意思是說一個人想去強銀行，但他又怕被抓，但他通過觀察計算出了在每個銀行被抓的概率，最後他提出如果他能承受最大被抓的概率，現在他想知道，在他能忍受的情況下，他能搶得的最大金額。

題解：這一題屬於0-1背包的變種題，它與那些常規的題目的不同之處主要體現在如下方面：

　　（1）在普通的0-1背包問題中只要確定了：volume與value變數，下麵就比較方便做了，但這一題有點改變，我們應該用每個銀行打算搶多少錢的總數你來做volume變數。

　　（2）通常的0-1背包問題需要我們直接求題目問我們的最大值，而在這裡需要我們從另外一個方面來求它的最大值　　

　　（3）一般的0-1背包問題中dp數組中一般存貯的是我們要求的屬性值，這一題我們要求的屬性值是他能搶到的最大金額，而在這裡如果這樣做的話，可能會比較麻煩，所以這裡使用它來存儲在搶到j的時候的逃脫概率，是一個double類型的值。

　　（4）最後遍歷輸出的時候，當（1-dp[i]<=P）的時候，表示他在能承受的範圍內，能搶到的最大金額為i，遍歷整個數組，取最大值即可。

代碼：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int main(){
 6     int T;
 7     double P;
 8     int N;
 9     cin>>T;
10     while(T--){
11         scanf("%lf%d",&P,&N);
12         int M[20000]={0};
13         double Pj[20000]={0}; 
14         int sum=0;
15         for(int i=1;i<=N;i++){
16             scanf("%d %lf",&M[i],&Pj[i]);
17             sum=sum+M[i]; 
18         }//數據輸入完畢
19         double dp[200000]={0};
20         dp[0]=1;//搶了  0  萬元 成功逃跑的概率為 1  
21         for(int i=1;i<=N;i++){
22             for(int j=sum;j>=M[i];j--){
23                 dp[j]=max(dp[j],dp[j-M[i]]*(1-Pj[i]));
24             } 
25         }
26         int ans=0;
27         for(int i=sum;i>=0;i--){
28             if(1-dp[i]<=P){
29                 ans=max(ans,i);
30                 break;
31             }
32         }
33         cout<<ans<<endl;
34     }
35     return 0;
36 }