HDU - 2955
来源：https://vjudge.net/problem/HDU-2955
不好理解的 01背包
关键 ：用成功逃走的概率当做价值,银行的总钱数当做背包容量
思路：题目中给定价值和被抓几率，但是被抓几率不可以用乘积来组合计算，举个例子，比如第一个银行3%被抓几率，第二个5%被抓几率，那么乘起来会变成0.15%，抢的越多，被抓几率却越小了，显然不对，因此要转换成不被抓几率，上述例子则变为第一家97%不被抓，第二家95%不被抓，乘起来就是92.15%，抢的越多，不被抓的几率越来越小即被抓几率越来越大，这样才是符合常理的。
那么背包体积应该是什么呢？先看最普通01背包，用数个cost来填充V，使得value之和尽量大，那么这题就应该是用数个money填充总money，使得不被抓几率尽量大。那转移方程就是dp[j]=max（dp[j]，dp[j-w]*c），这里和01背包的区别就是从+改成了*。然后得到dp数组是0~V情况下的不被抓几率的最优（大）值，这根答案有什么关系？逆序枚举每一种情况，若此情况下的dp值即不被抓几率大于等于题目中所给的不被抓几率，那就输出，逆序着从大到小枚举保证了找到的一个解是最优解。
#include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <cstring> using namespace std; double dp[10010]; int a[110]; double cost[110]; int main() { int t; scanf("%d",&t); while(t--) { double k; int n,sum = 0; scanf("%lf %d",&k,&n); k = 1 - k; memset(dp,0,sizeof(dp)),memset(cost,0,sizeof(cost)),memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { scanf("%d %lf",&a[i],&cost[i]); cost[i] = 1.00 - cost[i]; sum += a[i]; } dp[0] = 1; for(int i=1;i<=n;i++) { for(int j=sum;j>=a[i];j--) { dp[j] = max(dp[j],dp[j-a[i]]*cost[i]); } } for(int i=sum;i>=0;i--) { if(dp[i] >= k) { printf("%d\n",i); break; } } } return 0; }
华为工作强度 816人发布