今天特地挑着背包问题做的,
所以一直苦思冥想,这个价值是 浮点型啊,这怎么整?
想到上一题的背包概率问题,加上参考其他人的做法,
但不要理解错题意,总的概率不等于在各个银行不被抓概率的总和,在这里要做一个简单的转化,把每个银行的储钱量之和当成背包容量,然后概率当成价值来求。这里是被抓的概率,我们把它转化成不被抓的概率,然后这里的和就可以转化成乘积了,这样一来,我们就得到一个可以垒乘的状态转移方程(传统的背包上是垒加),我们求出抢j钱的最大不被抓概率,最后再枚举一下就行了。这就转化成了01背包问题。
令f[i][j]表示在前i个银行中偷得的money为j时能
够逃脱的最大概率,这样以来便可以写出状态转移方程:f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]*(1-p[i])},其中我们设第i个银行中money为c[i] millon,
被caught的概率为p[i]。
用一维数组,简化,状态转移方程:f[j]=Max(f[j],f[j-c[i]]*(1-p[i]));
dp[j]表示的是:能抢j 钱不被抓到的概率;
代码附上:
#include<iostream> #include<cstring> using namespace std; int c[101],V; double f[10005],p[101]; void ZeroOnePack(int cost,double worth) //01背包def { for(int i=V;i>=cost;i--) if(f[i]<f[i-cost]*worth) //取最大值 f[i]=f[i-cost]*worth; } int main() { int T,n,i,j; double P; cin>>T; while(T--) { cin>>P>>n; V = 0; for(i = 0; i < n; i++) { cin>>c[i]>>p[i]; //c[i]为消耗cost,p[i]为价值,只是表示形式是概率 p[i] = 1.0 - p[i]; //不被抓的概率 V += c[i]; // V为背包容量, } for(i = 1; i <= V; i++) //初始化,除f[0] = 1.以外,其余都为0.0. f[i] = 0.0; f[0] = 1.0; //没抢钱不被抓的概率为1 for(i = 0; i < n; i++) //背包 ZeroOnePack(c[i],p[i]); for(int j = V; j >= 0; j--) //查找在不被抓的情况下最大的的获得 { if(f[j] >= 1.0-P) { cout<<j<<endl; break; } } } return 0; }
2013年04月16日 19:49:29 再次复习提交:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <iomanip> double dp[10005]; using namespace std; double max(double a, double b) { return a>b?a:b; } int main(int argc, char *argv[]) { int T,n,M[105]; double p,P[105]; scanf("%d",&T); while(T--) { scanf("%lf%d",&p,&n); int V = 0; for(int i = 0; i < n; i++) { scanf("%d%lf",&M[i],&P[i]); P[i] = 1.0-P[i]; V += M[i]; } memset(dp,0,sizeof(dp)); dp[0] = 1.0; for(int i = 0; i < n; i++) { for(int j = V; j >= M[i]; j--) dp[j] = max(dp[j-M[i]]*P[i],dp[j]); } for(int i = V; i >= 0; i--) { if(dp[i]>=1.0-p) { cout<<i<<endl; break; } } } return 0; }