题目:http://acm.hdu.edu.cn/showproblem.php?pid=2955
题目大意:有一个小偷要偷银行的钱,可是他偷没家银行总是有一定的概率被抓,现在给了你一个概率P,
只要他被抓的概率乘积不大与P,他就是安全的。问你在他安全的情况下,他最多可以偷多少钱。
容量为银行钱的总和,价值就是偷到的钱,花费就是被抓的概率。
dp方程:dp[j] = Max(dp[j],dp[j-w[i]]*(1-p[i]))
#include<stdio.h> #include<ctype.h> #include<string.h> int w[101]; float dp[10005]; int main() { int t,n,i,j,sum; float p,c[101]; scanf("%d",&t); while( t-- ) { scanf("%f%d",&p,&n); sum = 0; for(i = 0; i < n; i++) { scanf("%d%f",w+i,c+i); sum += w[i]; } memset(dp,0,sizeof(dp)); dp[0] = 1;// 如果偷0元的话概率为1,所以dp[0]初始化为1; for(i = 0; i < n; i++) for(j = sum;j >= w[i]; j--) { if(dp[j] < dp[j-w[i]]*(1-c[i])) dp[j] = dp[j-w[i]]*(1-c[i]); } for(i = sum; i >= 0; i--) if(dp[i] >= 1-p) { printf("%d\n",i); break; } } } return 0; }