hdu2955robberies

リュック9の中の01リュックの1種の変形
プロトタイプdp[v]=max(dp[v],dp[v-c[i]+w[i]);
本題を分析する.
リュック容量=全銀行の金額の和sum+=c[i]i=0,1…n;
お金は掴まれた確率で価値は盗まれたお金です
従って、dp[v]=max(dp[v],dp[v-c[i]*w[i])を推定することは難しくない.dpがdouble型の精度は2桁以上であることに注意
コードは次のとおりです.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    int t;
    cin>>t;
    double dp[10000],p;
    double w[100];
    int c[100],n;
    while(t--)
    {
        cin>>p>>n;
        int count=0;
        for(int i=0;i<n;i++)
        {
            cin>>c[i]>>w[i];
            count+=c[i];
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1.0;
        for(int i=0;i<n;i++)
            for(int v=count;v>=c[i];v--)
                dp[v]=max(dp[v],dp[v-c[i]]*(1-w[i]));
        for(int i=count;i>=0;i--)
        {
            if(dp[i]>=1-p)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}