对于100瓦的实例，我认为基于输入图的雕刻分解的动态程序可以适应账单。
雕刻分解
在图论中，图的雕刻分解是其顶点的递归二进制分区。例如，这是一张图
1--2--3
| |
| |
4--5
和其雕刻分解之一
{1,2,3,4,5}
/ \
{1,4} {2,3,5}
/ \ / \
{1} {4} {2,5} {3}
/ \
{2} {5}.
雕刻分解的宽度是离开其一个分区的最大边缘数。在这种情况下，{2,5}具有出发边2–1,2-3和5–4，因此宽度为3.10×10网格的kd-tree风格分区的宽度是13。
图形的雕刻宽度是雕刻分解的最小宽度。已知具有n个顶点的平面图(特别是网格图的子图)具有雕刻宽度O(√n)，并且大O常数相对较小。
动态程式
给定n顶点输入图和宽度w的雕刻分解，有一个O(2w n)时间算法来计算最优瓦片选择。这个运行时间在w中快速增长，所以您应该尝试用手分解一些示例输入，以了解要预期的性能。
该算法从下向上对分解树工作。让X是一个分区，让F是离开X的边的集合。我们制作一个映射每个2 | F |的表在F的存在或不存在边缘的情况下，在指定的约束条件下，X上的最优总和(-Infinity，如果没有解)。例如，使用分区{1,4}，我们有条目
{} -> ??
{1--2} -> ??
{4--5} -> ??
{1--2,4--5} -> ??
对于仅具有一个顶点的叶分区，F的子集完全确定瓦片，因此可以很容易地填充连接数(如果瓦片有效)，否则为-Infinity。对于其他分区，当计算表的条目时，请尝试两个子节点之间的边缘的所有不同连接模式。
例如，假设我们有碎片
|
. .- .- -. .
|
{1}的表是
{} -> 0
{1--2} -> 1
{1--4} -> -Infinity
{1--2,1--4} -> 2
{4}的表是
{} -> 0
{1--4} -> 1
{4--5} -> 1
{1--4,4--5} -> -Infinity
现在我们来计算{1,4}的表。对于{}，没有边缘1–4，{1}(条目{})的得分为0，{4}(条目{})的得分为0。边缘1–4，我们得到-Infinity 1 = -Infinity(条目{1–4})。
{} -> 0
对于{1–2}，得分为1 0 = 1，不含1–4和2 1 = 3。
{1--2} -> 3
继续。
{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity))
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity))
最后，我们可以使用这些表来确定最优解。
寻找雕刻分解
有一些复杂的算法来找到很好的雕刻分解，但你可能不需要它们。尝试一个简单的二进制空间分区方案。
如果觉得《用计算机算法拼拼图 算法 – “拼图拼图”拼图》对你有帮助，请点赞、收藏，并留下你的观点哦！
