题目描述
夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生 日礼物。
商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种 礼物的喜悦值不能重复获得）。
每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。 季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到，也 算一次购买。
众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。
求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期 望购买次数。
题目描述
夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生 日礼物。
商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种 礼物的喜悦值不能重复获得）。
每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。 季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到，也 算一次购买。
众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。
求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期 望购买次数。
输入
第一行，一个整数N，表示有N种礼物。
接下来N行，每行一个实数Pi和正整数Wi，表示第i种礼物被拿出来的概率和 可以获得喜悦值。
输出
第一行，一个整数表示可以获得的最大喜悦值。
第二行，一个实数表示获得这个喜悦值的期望购买次数，保留3位小数
样例输入
3
0.1 2
0.2 5
0.3 7
样例输出
14
12.167
对于10%的数据，N = 1
对于30%的数据，N ≤ 5
对于100%的数据，N ≤ 20 ，0 < Wi ≤ 10^9 ，0 < Pi ≤ 1且∑Pi ≤ 1
考试时一看数据范围就知道是个状压，但凡是和概率dp结合起来就根本不会啊，只能qj测试点拿10分，考试的时候还怀疑测试点为什么不是三个概率取倒数加起来，
然后就只能拿10分滚粗了。（后来动动dalao解释说是因为他每次都有概率之和的概率拿出物品，有该物品的概率拿出该物品，这就显然不是概率之和了）。
我们先设计zt，设dp[sta]为状态为sta的期望数，其中若第i位为1表示没买过，0表示买过
然后就可以愉快的转移了
$dp[i]=\Sigma{p[j]*dp[i|(1<<(j-1))]}+(1-\Sigma{p[j]})*dp[i]+1$
后面那一块就是转移到自己的概率。
然后化简一下，就变成了
$dp[i]=(\Sigma{p[j]*dp[i|(1<<(j-1))]}+1)/(\Sigma{p[j]})$
倒着枚举正着枚都行，博主是倒着枚举的，毕竟概率题套路嘛。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 double p[22],f[1<<22|1]; 9 int w[22]; 10 int main(){ 11 int n; 12 scanf("%d",&n); 13 long long resss=0; 14 for(int i=1;i<=n;i++){ 15 scanf("%lf%d",&p[i],&w[i]); 16 resss+=w[i]; 17 } 18 printf("%lld\n",resss); 19 int Max=(1<<n)-1; 20 f[Max]=0; 21 for(int i=Max-1;i>=0;i--){ 22 double pos=0.0,res; 23 for(int j=1;j<=n;j++){ 24 if(i&(1<<(j-1))) continue; 25 f[i]+=f[i|(1<<(j-1))]*p[j]; 26 pos+=p[j]; 27 } 28 f[i]=f[i]+1.0; 29 f[i]=f[i]*1.0/pos; 30 //cout<<f[i]<<endl; 31 } 32 printf("%.3lf",f[0]); 33 }
原文：https://www.cnblogs.com/leom10/p/11196378.html
