HDU2955 01 가방 변형

1081 단어
dp[i][j]: 이전 i개 은행에서 어떤 집을 강탈하여 j가치를 얻고 잡히지 않을 확률을 나타낸다.
dp[ j ]=max( dp[ j ],dp[ j - val[ i ] ]*( 1-w[ i ] ) ) );
모든 은행의 돈을 배낭의 최대 부피로 삼다
그러면 각 은행의 돈은 물품의 부피로 삼는다
그럼 잡힐 확률을 물건의 가치로
그러면 우리가 필요로 하는 동적 방정식을 쉽게 내놓을 수 있다.
dp[i]=max(dp[i],(dp[i-money]*(1-rp)));//머니 현재 은행돈,rp 현재 잡힐 확률
#include
#include
using namespace std;
double dp[10050];
int money[10050],sum,n;
double rp[10050];
int main()
{
    int t,i,j;
    double p;
    scanf("%d",&t);
    while(t--)
    {
      scanf("%lf%d",&p,&n);
      memset(dp,0,sizeof(dp));
      sum=0;
      for(i=0;i
      {
        scanf("%d%lf",&money[i],&rp[i]);
        sum+=money[i];
      }
      dp[0]=1;
      for(i=0;i
      {
        for(j=sum;j>=money[i];j--)
        {
           dp[j]=max(dp[j],dp[j-money[i]]*(1-rp[i]));
        }
      }
      for(i=sum;i>=0;i--)
      {
        if(dp[i]>1-p)
        {
           printf("%d
",i);break; } } } // system("pause"); return 0; }

좋은 웹페이지 즐겨찾기