HDU 2955 Robberies （轉化概率-01背包）

HDU 2955 Robberies （轉化概率-01背包）

代碼：

/*
* Problem: HDU No.2955
* Running time: 46MS
* Complier: G++
* Author: ACM_herongwei
* Create Time: 15:01 2015/9/9 星期三
* zeroonebags
* 用成功逃走的概率當做價值！銀行的總錢數當做背包容量！單個銀行的錢數體積，然後zeronebags
*/
#include 
#include 
#include 
#include 
#define CLR(c,v) (memset(c,v,sizeof(c)))
using namespace std;

template 
inline _T Max(_T a,_T b){
    return (a>b)?(a):(b);
}
template 
inline _T Maxx(_T a,_T b,_T c){
    return (a>Max(b,c))?(a):(Max(b,c));
}
const int N  = 1e4+ 10;

double dp[N];
int volume[N];
double p_value[N];

int main()
{
    int Ncase;
    scanf(%d,&Ncase);
    while(Ncase--)
    {
        CLR(dp,0);
        CLR(volume,0);
        CLR(p_value,0);
        double P;
        int n_banks;
        int sum_v=0;
        scanf(%lf %d,&P,&n_banks);
        P=1.0-P;                      // 逃走的概率
        for(int i=0; i=volume[i]; --j)
            {
                if(dp[j]<=dp[j-volume[i]]*p_value[i]) //注意是相乘！
                {
                    dp[j]=dp[j-volume[i]]*p_value[i];
                }
            }
        }
        int i;
        for(i=sum_v; i>=0; --i) //從總價值往前計算，判斷相應的概率
        {
            if(dp[i]>=P)
            {
                break;
            }
        }
        printf(%d
,i);
    }
    return 0;
}
/*
sample input
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
sample ouput
2
4
6
*/