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

Question

我的问题可以简化为：

我有 11 个 integersc(balls)（编号从 1 到 11）和 4 个盒子（bins）（盒子 A, B, C, D）。我想计算 11 整数分布到 4 框中的数量，满足以下约束：

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

我有一个列表，其中包含 11 个整数和它们喜欢的方框（表示为 x->A,B,C,D，可以读作 "integer x likes boxes 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

你的方法听起来不错。

选择一种方式来表示球在盒子中的分布（例如数组，以球为索引，盒子为值）。

写一个函数 isDistributionValid(distribution) 接受一个分布，如果所有约束都满足则 returns true。您可能需要编写以下辅助函数：

getBallsInBox(distribution, box)：return 是一个列表，其中包含分配给 box 的所有球
count(distribution, box)：returns分配给box的球数
anyPairSumsToTarget(list, target): returns true 如果 list 中的任何一对值总和为 target（提示：使用两个嵌套的 for 循环）

在 11 个循环的最里面，用当前分布的表示调用 isDistributionValid。如果结果为真，则增加一个计数器。

递归求解

有一种使用递归的更优雅的方法。重复代码少，球数不必固定。思路是写一个函数

count_distributions(current_ball, last_ball, distribution)

调用该函数时，current_ball之前的所有球应该已经分配到盒子中，并且分配应该存储在distribution中。函数 returns 可以通过将剩余的球分配给盒子来产生有效分布的数量。为此，该函数遍历 current_ball 的可能框，并针对每种可能性递归调用 count_distributions(current_ball+1, last_ball, new_distribution) 并对结果求和。作为基本情况，如果 current_ball 大于 last_ball，则分布完成，函数应检查分布是否有效，return 如果有效则为 1，如果无效则为 0'吨。该功能使用 count_distributions(1, 11, empty_distribution).

启动

伪代码：

function count_distributions(current_ball, last_ball, distribution):
    if current_ball > last_ball:
        // all the balls have been distributed
        if distribution is valid:
            return 1
        else
            return 0
    sum = 0
    // try each possibility for current_ball
    for chosen_box in boxes that current_ball likes:
        new_distribution = copy(distribution)
        update new_distribution so current_ball maps to chosen_box
        // recursively try remaining balls
        sum += count_distributions(current_ball + 1, last_ball, new_distribution)
    return sum

print(count_distributions(1, 11, empty distribution))

优化

如果当前不完整的分发无效，可以通过提前终止来使两个版本显着加快。每次将（球，盒子）分配添加到分布中时，检查不完整分布是否有效。如果不是，则继续该分发没有意义。

可以通过向分布表示中添加更多信息来更有效地检查约束，但我不会详细介绍。

Answer 2

(1) 定义框类.

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);

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

Putting balls into bins while satisfying constraints

java

algorithm

combinatorics

brute-force

递归求解

优化