hdu 2955 Robberies 01背包問題

題目連結 題意：給出總機率P，銀行個數n。每個銀行有價值vi，被抓機率pi。求被抓機率不大于P所搶到的最大價值。 由于這題的機率是小數。我們把機率看成價值，價值看成容量。di表示的是搶到價值時最大不被抓率。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define INF 1e11
#define N 11000
using namespace std;

int w[N];
double v[N],d[N];

int main()
{
    int T,n;
    double p;
    cin>>T;
    while(T--)
    {
        scanf("%lf%d",&p,&n);
        int m=0,ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%lf",&w[i],&v[i]);
            m+=w[i];
        }
        memset(d,0,sizeof(d));
        d[0]=1;
        for(int i=0;i<n;i++)
            for(int j=m;j>=w[i];j--)
                d[j]=max(d[j],d[j-w[i]]*(1-v[i]));
        for(int i=m;i>=0;i--)
            if(d[i]>=1-p)
            {
                cout<<i<<endl;
                break;
            }
    }
}