java - 在满足约束的情况下将球放入容器中

Question

我的问题可以简化为:

我有11 integersc(balls)(编号从 1 到 11)和 4箱子(箱子)(箱子 A, B, C, D )。我想计算 11 的分布数量整数到 4满足以下约束的框:

• 盒子A容量为 1(一次只能容纳 1 个整数)
• 盒子 B, C, D不能包含 2 个总和为 13 的整数
• 一个整数只能放在它喜欢的盒子里。

我拥有的是那些 11 的列表整数和他们喜欢的盒子(表示为 x->A,B,C,D 可以读作“整数 x 喜欢盒子 A、B、C、D”):

1->(A, D) , 2->(B) , 3->(B) , 4->(B) , 5->(B) , 6->(C) , 7->(C,D) , 8->(C,D) , 9->(C,D) , 10->(C,D) , 11->(D) .

在这种情况下，解决方案是 8，有 8 种可能的方式在方框之间分配整数:

A=[1]、B=[2,3,4,5]、C=[6,8,9,10]、D=[7,11] 和另外 7 个分布，其中 8,9,10在盒子 C 和 D 中分布不同。

现在在纸上这样做很好，但我正在努力寻找一种系统的方法(蛮力)来遍历所有满足约束的可能分布。我的方法包括 11 个 for 循环(每个数字一个)，每个循环遍历一个列表(每个数字都有一个列表，里面装满了它喜欢的框)。我在计算分布数量的同时尝试强制执行约束时迷失了方向，是否有更优雅、更通用的方法在满足某些约束问题的同时将这些球解决成箱子？

Answer 1

(1)定义Box类。

abstract class Box {

    Set<Integer> balls = new HashSet<>();
    abstract boolean canAdd(int n);

    boolean add(int n) {
        if (!canAdd(n)) return false;
        balls.add(n);
        return true;
    }

    void remove(int n) { balls.remove(n); }
    @Override public String toString() { return balls.toString(); }
}

class Box1 extends Box {
    // has a capacity of 1 (only 1 integer fits into it at one time)
    boolean canAdd(int n) {
        return balls.size() < 1;
    }
}

class Box13 extends Box {
    // cannot contain 2 integers which sum up to 13
    boolean canAdd(int n) {
        int remain = 13 - n;
        return !balls.contains(remain);
    }
}

(2) 定义实际的盒子。

Box A = new Box1();
Box B = new Box13();
Box C = new Box13();
Box D = new Box13();

(3) 定义整数的偏好。

Box[][] likes =  {
    /*  0 */ {},
    /*  1 */ {A, D},
    /*  2 */ {B},
    /*  3 */ {B},
    /*  4 */ {B},
    /*  5 */ {B},
    /*  6 */ {C},
    /*  7 */ {C, D},
    /*  8 */ {C, D},
    /*  9 */ {C, D},
    /* 10 */ {C, D},
    /* 11 */ {D},
};

(5) 寻找解决方案。

for (Box b1 : likes[1]) {
    if (!b1.add(1)) continue;
    for (Box b2 : likes[2]) {
        if (!b2.add(2)) continue;
        for (Box b3 : likes[3]) {
            if (!b3.add(3)) continue;
            for (Box b4 : likes[4]) {
                if (!b4.add(4)) continue;
                for (Box b5 : likes[5]) {
                    if (!b5.add(5)) continue;
                    for (Box b6 : likes[6]) {
                        if (!b6.add(6)) continue;
                        for (Box b7 : likes[7]) {
                            if (!b7.add(7)) continue;
                            for (Box b8 : likes[8]) {
                                if (!b8.add(8)) continue;
                                for (Box b9 : likes[9]) {
                                    if (!b9.add(9)) continue;
                                    for (Box b10 : likes[10]) {
                                        if (!b10.add(10)) continue;
                                        for (Box b11 : likes[11]) {
                                            if (!b11.add(11)) continue;
                                            System.out.printf("A=%s B=%s C=%s D=%s%n",
                                                A, B, C, D);
                                            b11.remove(11);
                                        }
                                        b10.remove(10);
                                    }
                                    b9.remove(9);
                                }
                                b8.remove(8);
                            }
                            b7.remove(7);
                        }
                        b6.remove(6);
                    }
                    b5.remove(5);
                }
                b4.remove(4);
            }
            b3.remove(3);
        }
        b2.remove(2);
    }
    b1.remove(1);
}

结果

A=[1] B=[2, 3, 4, 5] C=[6, 8, 9, 10] D=[7, 11]
A=[1] B=[2, 3, 4, 5] C=[6, 8, 9] D=[7, 10, 11]
A=[1] B=[2, 3, 4, 5] C=[6, 8, 10] D=[7, 9, 11]
A=[1] B=[2, 3, 4, 5] C=[6, 8] D=[7, 9, 10, 11]
A=[1] B=[2, 3, 4, 5] C=[6, 9, 10] D=[7, 8, 11]
A=[1] B=[2, 3, 4, 5] C=[6, 9] D=[7, 8, 10, 11]
A=[1] B=[2, 3, 4, 5] C=[6, 10] D=[7, 8, 9, 11]
A=[1] B=[2, 3, 4, 5] C=[6] D=[7, 8, 9, 10, 11]
A=[] B=[2, 3, 4, 5] C=[6, 8, 9, 10] D=[1, 7, 11]
A=[] B=[2, 3, 4, 5] C=[6, 8, 9] D=[1, 7, 10, 11]
A=[] B=[2, 3, 4, 5] C=[6, 8, 10] D=[1, 7, 9, 11]
A=[] B=[2, 3, 4, 5] C=[6, 8] D=[1, 7, 9, 10, 11]
A=[] B=[2, 3, 4, 5] C=[6, 9, 10] D=[1, 7, 8, 11]
A=[] B=[2, 3, 4, 5] C=[6, 9] D=[1, 7, 8, 10, 11]
A=[] B=[2, 3, 4, 5] C=[6, 10] D=[1, 7, 8, 9, 11]
A=[] B=[2, 3, 4, 5] C=[6] D=[1, 7, 8, 9, 10, 11]

递归求解器是

static void solve(Box A, Box B, Box C, Box D, Box[][] likes, int n) {
    if (n > 11) {
        System.out.printf("A=%s B=%s C=%s D=%s%n", A, B, C, D);
        return;
    }
    for (Box box : likes[n]) {
        if (!box.add(n)) continue;
        solve(A, B, C, D, likes, n + 1);
        box.remove(n);
    }
}

和

solve(A, B, C, D, likes, 1);