algorithm - 如何获得所有最小套装封面？

Question

集合覆盖算法往往只提供一种解决方案来找到要覆盖的最小数量的集合。如何去寻找所有这些解决方案？

Answer 1

这取决于您所说的“最小”是什么意思，因为这会改变您获得的套装封面数量。例如，如果您有目标集ABC和AB,可供选择AC，C您可以覆盖 ( AB, C) 或 ( AB, AC) 或所有 3 ( AB, AC, C) 并且如果您将“最小”定义为例如 2最低选择，即重叠最少或重复元素最少，那么您将选择第一个 2 (( AB, C) 和 ( AB, AC))。“最小”也可以根据选择的集合数来定义，因此对于上面的示例，最小的数字是 2 和 ( AB, C) 或 ( AB,AC） 会工作。但是，如果您想要所有可能的套装封面，您可以从蛮力开始通过每个组合，所以

import java.util.*;
public class f {

    // abcd
    static int target = 0b1111;
    // ab,ac,acd,cd
    static int[] groups = {0b1100,0b1010,0b1011,0b0011};

    // check if sets cover target
    // for example 1100 and 0011 would cover 1111
    static boolean covers(boolean[] A){
        int or = 0;
        for(int i=0;i<A.length;i++){
            if(A[i]) or = or | groups[i];
        }
        int t = target;
        while (t>0){
            if(t%2!=1 || or%2!=1)
                return false;
            t = t>>1;
            or = or>>1;
        }
        return true;
    }

    // go through all choices
    static void combos(boolean A[],int i,int j){
        if(i>j){
            if(covers(A)) System.out.println(Arrays.toString(A));
            return;
        }
        combos(A,i+1,j);
        A[i]=!A[i];
        combos(A,i+1,j);
    }

    public static void main(String args[]){
        boolean[] A = new boolean[groups.length];
        combos(A,0,groups.length-1);
    }
}