首页 > 代码库 > HDU 2955 Robberies --01背包变形
HDU 2955 Robberies --01背包变形
这题有些巧妙,看了别人的题解才知道做的。
因为按常规思路的话,背包容量为浮点数,,不好存储,且不能直接相加,所以换一种思路,将背包容量与价值互换,即令各银行总值为背包容量,逃跑概率(1-P)为价值,即转化为01背包问题。
此时dp[v]表示抢劫到v块钱成功逃跑的概率,概率相乘。
最后从大到小枚举v,找出概率大于逃跑概率的最大v值,即为最大抢劫的金额。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 10007 int c[102]; double w[102],dp[N]; //dp[i]:抢劫到i块钱成功逃跑的概率 int main() { int t,n,i,sum,v,V; double Vf; scanf("%d",&t); while(t--) { scanf("%lf%d",&Vf,&n); Vf = 1 - Vf; V = 0; for(i=1;i<=n;i++) { scanf("%d %lf",&c[i],&w[i]); w[i] = 1 - w[i]; V += c[i]; } memset(dp,0,sizeof(dp)); dp[0] = 1.0; //抢到0块钱逃跑概率为1.0 for(i=1;i<=n;i++) { for(v=V;v>=c[i];v--) dp[v] = max(dp[v],dp[v-c[i]]*w[i]); } for(i=V;i>=0;i--) { if(dp[i] >= Vf) break; } printf("%d\n",i); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。