hdu 2955 Robberies(01背包變形)

思路：將各個銀行的總資產當做背包的容量V，然後求最大的逃跑率

初始化：搶劫的金額為0時，一定是安全的，所以d[0]=1；其他金額初始為逃跑概率最小，全為0

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
double d[10005],v[105];
int c[105];
int main()
{
    int T,n,i,j;
    double p;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf%d",&p,&n);
        p = 1 - p;//1-p為最低逃跑概率，小於1-p均會被抓
        int V = 0;
        for(i = 0 ; i < n ; i ++)
        {
            scanf("%d%lf",&c[i],&v[i]);
            v[i] = 1 - v[i];//題目給的是被抓的概率，需先轉化為逃跑的概率
            V += c[i];//各個銀行的總資產
        }
        memset(d,0,sizeof(d));
        d[0] = 1;
        for(i = 0 ; i < n ; i ++)
        for(j = V ; j >= c[i] ; j --)
        d[j] = max(d[j],d[j - c[i]] * v[i]);
        for(i = V ; i >= 0 ; i --)
        if(d[i] - p >= 0.000000001)
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}