题意：传送门
题解：用dp[i][j]代表从第i个宝物开始，当前状态（已经取过的宝物）为j的情况下，用最优策略应对，到最后可以取得的分数的期望值。因为当前这一轮出现任何宝物的几率相等，所以期望值等于 所有情况下期望得分的和 除以 情况数。而出现第k种宝物的情况下，期望得分为max(dp[i+1][j],dp[i+1][j|1<<k] + P[k])。所以，转移方程为
dp[i][j]=Σ(1<=k<=N)max(dp[i+1][j],dp[i+1][j|1<<k] + P[k]) / N。
dp[i][j],i>N的情况是基础情形，期望得分为0。
那么，如何根据已有的结果，得到最优应对策略呢？假设当前正在出现第i个宝物，状态为j，出现了第k种宝物。如果状态j不满足要求，自然不收取宝物。否则，如果dp[i+1][j]>dp[i+1][j|1<<k]+P[k]，则说明不收取的期望收益大，反之则是收取的期望收益大。
最后直接记忆化搜索即可。
附上代码：
第二种是使用倒推，因为正推对于dp[i][s]，可能在第i轮到不了s这个状态，依然用dp[i][j]代表从第i个宝物开始，当前状态（已经取过的宝物）为j的情况下，用最优策略应对，到最后可以取得的分数的期望值。然后就能从后往前递推，如果对于第i种物品，能取的话，那么从取它和不取它导出最大值，如果不能取，直接加上后面的值即可，最后算期望，统一除以个数即可。
附上代码：