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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/47132.html
標籤：C++