本文主要是介绍hdu 2955 dp(0,1背包) Robberies，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个，刚开始，想的是所有人的想法，把概率乘到整数，然后0,1背包。
但是，想着要乘几位，于是看了下别人的。。。
没想到，是反过来，把抢的钱看成背包,把逃跑率看成价值。
dp[i][j]表示抢第i家银行要抢j的钱能逃跑的最大概率。
当money[i]<=j时，dp[i][j]=max(dp[i-1][j],dp[i-1][j-money[i]]*p[i]);
这里因为是概率问题，所以是相乘。
然后呢，当抢到j的钱能逃跑的最大概率要大于不被抓到概率，就表示，j的钱可以抢到。
最后，就是比较j的最大值了。。。
#include <iostream>
#include<string>
using namespace std;float max(float f1,float f2)
{return f1>f2?f1:f2;
}int main()
{
// freopen("in.txt","r",stdin);float dp[10005];float p[105];int m[105];int t,n,sm,i;float pp;scanf("%d",&t);while(t--){scanf("%f %d",&pp,&n);sm=0;for(i=0;i<n;i++){scanf("%d %f",&m[i],&p[i]);sm+=m[i];}for(i=0;i<=sm;i++)dp[i]=0;dp[0]=1;dp[m[0]]=1-p[0];for(int j=1;j<n;j++)for(int k=sm;k>=m[j];k--)dp[k]=max(dp[k],dp[k-m[j]]*(1-p[j]));
// cout<<dp[i]<<endl;for(i=sm;i>=0;i--)if(dp[i]>(1-pp))break;printf("%d\n",i);}return 0;
}
这篇关于hdu 2955 dp(0,1背包) Robberies的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
