lightoj 1079 - Just another Robbery 01 가방

1202 단어 dp가방
n개 은행이 있는데 은행마다 와이원을 약탈할 수 있다. 잡힐 확률은 pi이다. 잡힐 확률이 P에 도착하면 위험하다. 최대 얼마까지 약탈할 수 있는지 물어보면 위험에 빠지지 않는다.
뻔한 01가방..dp[i]는 i원을 약탈하여 가장 적게 잡힐 확률을 대표한다...그러나 계산이 비교적 번거로우니 바꿀 수 있다
dp[i]는 i원을 약탈하고 잡히지 않을 확률을 대표한다...
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define ll long long
double dp[11000],p[120];
int w[120];
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        int n;
        double P;
        int sum=0;
        scanf("%lf %d",&P,&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d %lf",&w[i],&p[i]);
            sum+=w[i];
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1.0;
        for(int i=0;i<n;i++)
        {
            for(int j=sum;j>=w[i];j--)
            {
                if(dp[j-w[i]]==0) continue;
                dp[j]=max(dp[j],dp[j-w[i]]*(1.0-p[i]));
            }
        }
        for(int i=sum;i>=0;i--)
        {
            if(P>=(1-dp[i]))
            {
                printf("Case %d: %d
",cas,i); break; } } } return 0; }

좋은 웹페이지 즐겨찾기