思路
设$f[i][S]$为第$1$个到第$i-1$个吃了的奖励的集合为$S$时,第$i$个到第$K$个的收益为$f[i][S]$
枚举当前出现的第$i$个奖励的种类$j$,若可以食用
$$f[i][S]=f[i][S]+\max\{f[i+1][S], f[i+1][S|1<<(j-1)]+P_j\}$$
若不可以食用
$$f[i][S]=f[i][S]+f[i+1][S]$$
代码
#include <iostream>
#include <cstdio>
int P[16], pre[16], n, K;
double f[110][1<<16];
int main(){
scanf("%d%d", &K, &n);
for(int i=1; i<=n; i++){
scanf("%d", &P[i]);
int x;
while(1){
scanf("%d", &x);
if(!x) break;
pre[i]|=1<<(x-1);
}
}
for(int i=K; i; i--)
for(int j=1; j<=n; j++)
for(int S=0; S<(1<<n); S++){
if((S&pre[j])==pre[j])
f[i][S]+=std::max(f[i+1][S], f[i+1][S|(1<<(j-1))]+P[j])/n;
else
f[i][S]+=f[i+1][S]/n;
}
printf("%.6lf", f[1][0]);
return 0;
}