Kyu*_*ubi 2 algorithm 2d matrix knapsack-problem dynamic-programming
在最近由“AmDocs”组织的比赛中，我遇到了以下问题：（问题的基本思想）
你是一个固定大小的矩阵 12x12。您将获得六个长度为 6、5、5、4、3、2 的线段。矩阵有空的空间和填充的空间。您必须返回 "Yes" 或 "No" ，无论所有 6 条线段是否可以同时适合矩阵。线条只能水平或垂直放置。
应该使用什么算法来解决这个问题？包装 ？背包？
我会将问题映射到 SAT 并使用 SAT 求解器。有一个非常自然的映射。定义变量：
x_s_i_j_d = segment s starts at coordinates (i,j) and goes in direction d
（d 是“右”或“下”）
首先，迭代所有段和起始位置，看看给定起始矩阵哪些是可行的。例如，M：
000000000000
111111111111
...
如果第 1 段的长度为 2，则L_seg1_0_0_down = false，因为它碰到了一个填充的空间。
然后，编写禁止两个交叉段的子句。如果段 1 和段 2 的长度都是 2，那么我们添加子句：
(!L_seg1_0_0_right || !L_seg2_1_0_right)
因为如果段 1 使用坐标 (0,0) 和 (1,0)，那么段 2 也不能使用 (1,0)。
最后，添加每个段必须至少使用一次的条件：
(L_seg1_0_0_right || L_seg1_0_1_right || ...)
对于 seg1 可以去的所有位置。然后把你最喜欢的 SAT 求解器扔给它。