包含/排除 n 个问题中的至少 x 个

Question

我需要解决一个概率问题，其中有人邀请了 n 位客人参加他的生日聚会。我得到一个整数 x 和一个包含 n 个条目的列表。每第 i 个条目都给出了第 i 个客人参加聚会的概率。

问题是找出至少 x 位客人将参加聚会的概率。 我知道这个问题有几种不同的更好的算法，但我想知道我是否可以用排除/包含原则来解决这个问题。

我试过这样做： -创建至少包含 x 个元素的任务概率列表的所有子集； -然后对于每个子集，将概率相乘，这应该给出至少子集中的那些客人将参加聚会的概率。

-添加基数为 x 或 x+k2 的子集的值； -减去基数为 x+1 +k2 的子集的值；

这最终不起作用，因为我得到的值远高于 1 或 -1。我在这里做错了什么？

如果我们从至少有 1 个元素的最基本子集开始，是否只能使用排除/包含原则？

    int x = 5;

    double[] guests = new double[] {0.34, 0.24, 0.72, 0.28, 0.55, 0.88, 0.91, 0.0.99, 0.01, 0.46};
    
    ArrayList<Double> subset = new ArrayList<Double>();
    ArrayList<ArrayList<Double>> Subsets = new ArrayList<>();
    getSubsets(subset,Subsets,0,guests,x);
    
    double probx = 0;
    
    for(int i = 0;i<Subsets.size();i++){
      double prob = 1;
      for(int j = 0;j<Subsets.get(i).size();j++){
        prob = Subsets.get(i).get(j)*prob;
      }
     
      if((Subsets.get(i).size()%x)%2==0){
          
        probx += prob;
      }else{
          
        probx -= prob;
      }
    }
    
    System.out.println(probx);
}
public static void getSubsets(ArrayList<Double> tmp, ArrayList<ArrayList<Double>> subsets, int i, double[] guests, int maxlength) {
  if(i==tage.length) {
    if(tmp.size()>=maxlength) {
      subsets.add(tmp);
    }
    return;
  }
  ArrayList<Double> newSet = new ArrayList<>(tmp);
  newSet.add(guests[i]);

  getSubsets(newSet,subsets,i+1,guests,maxlength);
  getSubsets(tmp,subsets,i+1,guests,maxlength);
}

Answer 1

你可能会用 Mote Carlo 模拟来解决这个问题。你有 n 变量伯努利分布，但每个伯努利样本都是独立的，所以

• 将计数设置为 0
• 使用伯努利以概率 p_i
模拟 n-dim {0,1} 向量
• sum 向量，如果 sum >= x，则递增 count
• 重复模拟N次，答案为count/N

不太了解 Java，可以用 Python 编写一些东西。如果您需要代码，请联系我