图论与组合优化在二维背包中的交叉应用

1/1图论与组合优化在二维背包中的交叉应用第一部分二维背包问题的数学描述 2第二部分图论中最大权匹配模型的构建 5第三部分组合优化方法中的动态规划算法 8第四部分图论算法在背包问题中的应用 11第五部分组合优化算法在图论问题中的应用 14第六部分混合策略的优点和缺点 17第七部分图论与组合优化交叉应用的前景 18第八部分二维背包问题求解实例 21

第一部分二维背包问题的数学描述关键词关键要点二维背包问题的定义

1.问题表述：给定一个物品集合，每个物品具有重量和价值，以及一个容量限制为W×H的二维背包。目标是在不超过背包容量的条件下，选择物品放入背包，使背包中的物品总价值最大化。

2.决策变量：选择每个物品是否放入背包的二元变量xᵢⱼ，其中i和j分别表示物品在重量和高度维度上的索引。

背包容量约束

1.容量限制：二维背包的容量为W×H，其中W和H分别表示背包在重量和高度维度上的最大承载能力。

2.放置约束：物品放入背包时，其重量不能超过W，高度不能超过H。

3.容量不足：当物品的重量或高度超过背包的容量时，该物品不能放入背包。

物品属性

1.重量：物品在重量维度上的大小，影响其对背包重量容量的占用。

2.高度：物品在高度维度上的大小，影响其对背包高度容量的占用。

3.价值：物品的固有价值，是优化目标函数中要最大化的量。

目标函数

1.最大化价值：目标函数旨在最大化背包中物品的总价值。

2.价值函数：价值函数f(x)表示背包中所选物品的总价值，与决策变量xᵢⱼ相关。

3.最优解：目标函数的最优解对应于背包中物品总价值最大的选择方案。

决策变量约束

1.二元约束：决策变量xᵢⱼ为0或1，表示物品是否放入背包。

2.非负约束：决策变量不能为负，确保物品不会被部分放入背包。

3.互斥约束：每个物品只能放入背包一次。

问题求解方法

1.动态规划：一种自下而上的方法，将问题分解为较小的子问题，逐步求解。

2.分支定界：一种尝试不同的决策方案，并在不满足约束条件时剪枝的方法。

3.启发式算法：一种基于经验和直观的算法，往往不能保证找到最优解，但可以获得近似解。二维背包问题的数学描述

问题陈述

二维背包问题是一个组合优化问题，目标是确定在满足容量约束的情况下，从一组给定物品中选择哪些物品以最大化总价值。与经典背包问题不同，二维背包问题考虑了物品的两个维度（体积和重量）。

数学模型

二维背包问题可以通过以下数学模型来描述：

目标函数：

```

```

约束条件：

体积约束：

```

```

重量约束：

```

```

非负性约束：

```

x_i,y_i≥0

```

其中：

*n是物品的数量

*\(c_i\)是第i个物品的价值

*\(x_i\)是第i个物品在第一个维度（体积）上选择的数量

*\(y_i\)是第i个物品在第二个维度（重量）上选择的数量

*\(v_i\)是第i个物品在第一个维度（体积）上的体积

*\(w_i\)是第i个物品在第二个维度（重量）上的重量

*\(V_1\)是第一个维度（体积）的总容量

*\(V_2\)是第二个维度（重量）的总容量

变量

\(x_i\)和\(y_i\)是整数变量，表示选择第i个物品在两个维度上的数量。

约束条件的含义

体积约束表示所选物品的总体积不能超过总容量\(V_1\)。重量约束表示所选物品的总重量不能超过总容量\(V_2\)。非负性约束确保所选数量是非负的。

目标

目标函数旨在最大化所选物品的总价值，其中\(c_i\)是第i个物品的价值。

特殊情况

*一维背包问题：如果\(V_1=V_2\)，二维背包问题将退化为经典一维背包问题。

*多维背包问题：二维背包问题可以推广到多维情况，其中物品被考虑有多个维度。第二部分图论中最大权匹配模型的构建关键词关键要点【最大权匹配模型的构建】

1.二分图的定义和性质：

-一个二分图是一个无向图，其中顶点可以分为两个不相交子集（称为两部分），并且每条边连接两部分中不同的顶点。

-二分图中最大权匹配问题是指找到一个匹配，使匹配边的权值之和最大。

2.最大权匹配算法：

-匈牙利算法：一种多项式时间算法，用于解决一般二分图中的最大权匹配问题，其复杂度为O(V^3)，其中V是图中顶点的数量。

-网络流算法：将最大权匹配问题转换为最小费用最大流问题，然后使用网络流算法（如Ford-Fulkerson算法或Edmonds-Karp算法）求解。

3.二重对偶性和匈牙利算法：

-匈牙利算法基于一种对偶性原理，即最小费用最大流问题和最大权匹配问题是双重的。

-匈牙利算法通过迭代地更新匹配和残余图，并维护一个交替路径，确保找到一个最大权匹配。

1.2.3.图论中最大权匹配模型的构建

在二维背包问题中，我们将物品集合表示为图中的顶点，而背包容量限制则表示为图中的边权。物品之间的兼容性可以用图中的边来表示，如果两个物品不兼容，则它们之间没有边。

模型构建

为了构建最大权匹配模型，我们首先将物品集合建模为一个二分图。在这个二分图中，一边是物品顶点，另一边是背包顶点。根据物品之间的兼容性，在物品顶点和背包顶点之间添加边。边的权重设置为物品的价值。

接下来，我们定义以下变量：

*x_ij：如果物品i分配给背包j，则为1，否则为0。

利用这些变量，我们可以表述最大权匹配模型如下：

目标函数：

最大化：Σ(i,j)x_ij*v_i

其中：

*v_i：物品i的价值

约束条件：

*容量约束：Σ(i)x_ij<=C_j∀j

*分配约束：Σ(j)x_ij<=1∀i

容量约束确保每个背包都不超载。分配约束确保每个物品只能分配给一个背包。二分性约束确保变量x_ij只能取0或1。

模型求解

最大权匹配模型可以通过各种算法求解，例如匈牙利算法或KM算法。这些算法的目标是找到一组匹配，使目标函数的值最大化。

匹配结果的解释

求解最大权匹配模型后，我们可以将匹配结果解释为二维背包问题的解。对于每条匹配的边，对应的物品被分配给对应的背包。匹配边的权重之和即为背包问题的最大价值。

模型的优点

图论中的最大权匹配模型为二维背包问题提供了一种有效且通用的求解方法。该模型的优点包括：

*建模灵活：它可以处理各种尺寸和类型的物品集合。

*求解效率：匈牙利算法等算法的运行时间是多项式的。

*可扩展性：模型可以轻松地扩展以处理其他背包问题约束，例如重量约束或体积约束。

模型的局限性

尽管图论模型功能强大，但也有一些局限性：

*NP-难性：随着物品和背包数量的增加，求解模型的计算量可能会大幅增加。

*近似算法：对于大型问题，可能需要使用近似算法来获得可接受的解。

*离散性：该模型仅考虑离散的物品价值和背包容量，可能无法处理连续变量。

总体而言，图论中的最大权匹配模型是解决二维背包问题的有力工具。它提供了一种建模灵活、求解高效的方法，但对于非常大的问题，计算复杂度和离散性的局限性需要考虑。第三部分组合优化方法中的动态规划算法组合优化方法中的动态规划算法

组合优化问题是计算机科学中的重要领域，涉及在一个有限的可行解集合中寻找最佳解。动态规划是解决这类问题的强大方法，它是一种自顶向下的优化技术。

动态规划算法的基本原理

动态规划算法将问题分解成较小的子问题，并依次解决这些子问题。它存储每个子问题的最优解，从而避免重复计算。该算法遵循以下步骤：

1.定义子问题：将原始问题分解成较小的、重叠的子问题。

2.构建递归关系式：描述如何使用子问题的最优解来计算当前子问题的最优解。

3.求解子问题：自顶向下计算每个子问题的最优解。

4.存储最优解：将每个子问题的最优解存储在一个表中，以便后续计算复用。

动态规划算法在二维背包问题中的应用

二维背包问题是一个经典的组合优化问题，涉及在容量和价值受限的情况下，从一组物品中选择一组物品以最大化总价值。

问题描述

给定：

*一组物品，每个物品有重量和价值

*两个背包，每个背包有容量上限

目标：

*选择一组物品，放入两个背包中，使得总价值最大化

算法实现

使用动态规划解决二维背包问题的步骤如下：

1.定义子问题

将问题分解为更小的子问题，其中子问题由一个背包的容量和一个物品的索引定义：

```

d(i,j)=最大价值，从前i个物品中选择，放入容量为j的背包中

```

2.构建递归关系式

子问题的最优解可以通过以下关系式计算：

```

d(i,j)=max(

d(i-1,j),//不选择第i个物品

d(i-1,j-w_i)+v_i//选择第i个物品，如果容量足够

)

```

其中：

*`w_i`是第`i`个物品的重量

*`v_i`是第`i`个物品的价值

3.求解子问题

使用递归关系式自顶向下计算每个子问题的最优解，从子问题`d(0,0)`开始。

4.存储最优解

将每个子问题的最优解存储在一个二维表`d`中，以便后续计算重用。

5.轨迹回溯（可选）

如果需要确定选择的物品，可以使用轨迹回溯步骤来重建解决方案。

时间复杂度

动态规划算法解决二维背包问题的時間复杂度为`O(nW)`,其中`n`是物品的数量，`W`是背包容量。

空间复杂度

算法的空间复杂度为`O(nW)`,用於存储子问题的最优解。

优势

动态规划算法在解决二维背包问题方面具有以下优势：

*准确性：算法保证找到最优解。

*效率：算法利用存储来避免重复计算，提高效率。

*可扩展性：算法可以很容易地扩展到具有更多背包或物品的变体问题。

总结

动态规划是解决组合优化问题的强大技术，它允许以渐进的方式解决复杂问题。在二维背包问题的情况下，动态规划算法提供了准确高效的解决方案，使其成为解决此类问题的首选方法之一。第四部分图论算法在背包问题中的应用关键词关键要点【应用图论算法解决背包问题】

1.将背包问题建模为图论问题，其中背包的容量限制被建模为图的边权，物品的价值和重量被建模为图的顶点的权重。

2.使用动态规划算法或贪心算法在图中查找最优路径，以找到满足背包容量限制和最大化物品价值的物品组合。

3.这种方法可以有效解决背包问题，时间复杂度为O(nW)，其中n是物品的数量，W是背包的容量。

背包问题的变体

1.在经典的背包问题基础上，考虑了各种变体，包括多重背包问题（每个物品有多个副本可用），无界背包问题（背包容量不受限制），分维背包问题（背包有多个隔间，每个隔间有自己的容量限制），多维背包问题（物品有多个属性，例如价值、重量和体积）。

2.为这些变体开发了专门的图论算法，以解决更复杂的问题实例。

3.这些算法通常涉及更高级的数据结构和优化技术，例如动态规划表和分支限界。

多目标背包问题

1.在现实世界中，背包问题经常涉及多个目标，例如最大化物品的价值、重量和体积，或最小化物品的成本。

2.图论算法可以扩展到处理多目标背包问题，通过使用帕累托最优解集来表示非支配解。

3.多目标优化算法，如NSGA-II和SPEA2，被用来求解这些问题，以找到一组满足所有目标的最佳解。

不确定背包问题

1.在不确定环境中，背包问题的输入数据，例如物品价值和重量，可能是未知的或不确定的。

2.图论算法可以与概率论和模糊逻辑相结合，以解决不确定背包问题。

3.这些算法使用概率分布或模糊集来表示不确定性，并应用鲁棒优化技术来找到在各种不确定性场景下都表现良好的解决方案。

启发式算法的应用

1.对于大规模的背包问题实例，完全枚举所有可能的物品组合可能是不可行的。

2.启发式算法，例如模拟退火、禁忌搜索和遗传算法，已被用于求解背包问题。

3.这些算法通过迭代地改进当前解来找到近似最优解，即使对于计算密集型问题也是一种高效且可扩展的方法。

前沿趋势和应用

1.图论算法在背包问题中的应用仍在不断发展，重点关注解决更复杂和现实的变体，如多目标、不确定性和大规模问题。

2.人工智能技术，如机器学习和深度学习，正在被探索用于设计更有效的图论算法。

3.背包问题的解决方案在各种领域都有应用，包括资源分配、任务调度和投资组合优化，推动了图论算法在这些领域中的进一步发展。图论算法在背包问题中的应用

图论算法在解决背包问题中发挥着重要作用。背包问题是一种组合优化问题，目标是在给定一组物品和背包容量的情况下，从这些物品中选择一个子集，使子集的总价值最大化，且子集的总重量不超过背包容量。

0-1背包问题

0-1背包问题是背包问题中最基本的形式，其中每个物品只能选择一次（即取或不取）。对于0-1背包问题，可以使用动态规划算法来求解。动态规划算法将问题分解为一系列子问题，然后通过逐步求解子问题来获得整体最优解。

动态规划算法的递推关系如下：

```

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]),

```

其中：

*i：当前物品的索引

*j：背包容量

*w[i]：第i个物品的重量

*v[i]：第i个物品的价值

*dp[i][j]：背包容量为j时，前i个物品的最大总价值

有界背包问题

有界背包问题是背包问题的推广，其中每个物品可以被选择多次，但每次选择的数量不能超过给定的上限。对于有界背包问题，可以使用图论算法来求解。

构建图论模型

将物品视为图中的节点，将容量视为图中的边权。对于每个物品，向图中添加一个源节点和一个汇节点，源节点到物品节点的边权为物品的价值，物品节点到汇节点的边权为物品的重量。对于背包容量，添加一个虚拟的源节点和汇节点，虚拟源节点到背包容量节点的边权为0，背包容量节点到虚拟汇节点的边权为背包容量。

求解最大流

通过图论中的最大流算法，可以求出图中从虚拟源节点到虚拟汇节点的最大流。最大流的值即为背包问题的最优解。

其他图论算法

除了最大流算法之外，还有一些其他的图论算法也可以用于求解背包问题，例如：

*最小割算法

*网络流算法

*分支定界算法

优势

图论算法在解决背包问题时具有以下优势：

*对于0-1背包问题，动态规划算法的复杂度为O(nW)，其中n为物品数量，W为背包容量。

*对于有界背包问题，图论算法的复杂度为O(n^2W)，其中n为物品数量，W为背包容量。

*图论算法可以处理各种背包问题的变体，例如多重背包问题、约束背包问题等。

应用

图论算法在背包问题的应用非常广泛，例如：

*资源分配

*任务调度

*背包整理

*广告投放

*投资决策第五部分组合优化算法在图论问题中的应用关键词关键要点【最小生成树】

1.克鲁斯卡尔算法：基于贪心策略，逐步选择权重最小的边，直到形成一棵生成树。

2.普里姆算法：基于优先队列，逐步选择与已选边集合相邻且权重最小的边，直到形成一棵生成树。

3.应用：网络设计、聚类分析和图像分割等领域。

【最短路径】

组合优化算法在图论问题中的应用

组合优化算法在图论问题中得到了广泛的应用，旨在解决有关图结构的优化问题。这些算法旨在找到满足给定约束条件的最佳或近似最优解。以下是组合优化算法在图论问题中的常见应用场景：

最短路径问题：

*Dijkstra算法：用于在加权图中从一个顶点到所有其他顶点的最短路径。它利用贪心策略，每次迭代选择具有最小距离的未访问顶点。

*Bellman-Ford算法：用于在加权图中，可能存在负权重的最短路径。它通过迭代松弛操作，系统地更新最短路径距离。

*Floyd-Warshall算法：解决两两最短路径问题，通过动态规划计算任意两顶点之间的最短路径。

最大流问题：

*Ford-Fulkerson算法：用于在流网络中寻找最大流，该流网络由源顶点、汇顶点和容量约束的边组成。它通过寻找增广路径来增加流。

*Edmonds-Karp算法：一种改进的Ford-Fulkerson算法，利用最大匹配技术来加速增广路径查找。

*Dinic算法：一种高效的算法，用于解决大规模流网络的最大流问题，它利用分层图技术来提升性能。

最小生成树问题：

*Kruskal算法：一种贪心算法，通过选择最小权重的边并将其添加到树中，逐步构建图的最小生成树。

*Prim算法：类似于Kruskal算法，但它从一个顶点开始，并逐步将最轻的边添加到树中。

*Borůvka算法：一种更快速但不太直观的算法，它通过合并最小生成树来构造图的最小生成树。

图着色问题：

*贪心着色：一种简单的算法，按照顶点的度从大到小依次为其着色，尽可能避免使用相同的颜色。

*Welsh-Powell算法：一种改进的贪心算法，在着色顺序上进行排序，使具有最大度的顶点最后被着色。

*最大独立集算法：用于找到图中大小最大的独立集，即没有边连接的顶点集合。它可以转化为图着色问题并使用贪心或启发式算法求解。

匹配问题：

*匈牙利算法：一种多项式时间算法，用于在二分图中寻找最大匹配。它通过增广路径和交替路径技术来操作匹配。

*Kuhn-Munkres算法：匈牙利算法的一个变体，适用于一般图，但时间复杂度更高。

*Edmonds-Karp算法：也可以用于解决匹配问题，其变体包括Hopcroft-Karp算法和Micali-Vazirani算法。

这些组合优化算法在各种图论问题中发挥着至关重要的作用，包括网络优化、路径规划、任务分配和资源管理。它们的有效性和效率使它们成为解决现实世界问题的重要工具。第六部分混合策略的优点和缺点混合策略的优点和缺点

在二维背包问题中，混合策略是一种将图论和组合优化技术相结合的求解方法。它兼顾了图论中最大匹配算法的快速求解能力和组合优化中动态规划算法的精确求解能力，从而实现了对二维背包问题的快速且精确求解。

#优点

1.快速求解：混合策略利用最大匹配算法来快速求得初始解。最大匹配算法的时间复杂度为O(E√V)，其中E为图中的边数，V为图中的节点数。对于二维背包问题，图的节点数和边数与物品的数量和背包容量成正比，因此混合策略的求解时间复杂度为O(N√M)，其中N为物品的数量，M为背包的容量。这比单纯使用动态规划算法求解的O(NM)时间复杂度有显著的提升。

2.精确求解：混合策略在利用最大匹配算法求得初始解后，再使用动态规划算法对初始解进行优化。动态规划算法的时间复杂度为O(NM)，但由于初始解已经接近最优解，因此动态规划算法的迭代次数大大减少，从而降低了整体求解时间。

3.适用范围广：混合策略不仅适用于一般二维背包问题，还适用于具有特殊限制的二维背包问题，例如多维度背包问题、有时间窗口约束的背包问题等。

#缺点

1.依赖最大匹配算法：混合策略的求解过程依赖于最大匹配算法的性能。如果最大匹配算法不能快速求得高质量的初始解，则混合策略的整体性能也会受到影响。

2.存储空间消耗：混合策略在求解过程中需要存储大量的中间结果，这可能会对内存空间造成较大的消耗。尤其是对于大规模的二维背包问题，存储空间消耗可能会成为限制因素。

3.不保证全局最优解：混合策略虽然能够求得高质量的解，但不能保证求得的解是全局最优解。这是由于最大匹配算法本身不能保证求得的最大匹配是全局最优匹配，而动态规划算法也不能保证从初始解出发能找到最优解。

总体而言，混合策略在二维背包问题求解中具有快速求解、精确求解和适用范围广的优点，但也存在依赖最大匹配算法、存储空间消耗和不保证全局最优解的缺点。对于求解时间敏感且求解精度要求较高的二维背包问题，混合策略是一种非常有效的求解方法。第七部分图论与组合优化交叉应用的前景图论与组合优化在二维背包中的交叉应用

前景

图论与组合优化在二维背包问题中的交叉应用前景广阔，主要体现在以下几个方面：

复杂问题建模：

二维背包问题是一个NP难问题，利用图论可以将问题建模为一个图，其中顶点表示物品，边表示物品之间的关系。这种建模方法可以简化问题的复杂性，便于使用组合优化算法进行求解。

算法改进：

图论模型可以为组合优化算法提供新的思路，例如：

*最长路径算法：基于图的宽度优先搜索或深度优先搜索算法可以求解二维背包问题中的一些变种，如多重背包问题。

*分支定界：图模型可以指导分支定界算法的搜索策略，减少搜索空间，提高求解效率。

启发式算法设计：

图模型可以作为启发式算法设计的基础，例如：

*禁忌搜索：基于图的禁忌搜索算法可以避免搜索陷入局部最优解，提高解的质量。

*遗传算法：图模型可以表示物品之间的基因关系，辅助遗传算法进行交叉和变异操作。

大規模問題求解：

隨著資料規模不斷擴大，傳統組合優化算法難以滿足大規模問題求解需求。圖論和組合優化的交叉應用可以提供新的思路，例如：

*並行算法：圖模型可以被分解成子圖進行並行計算，提高大規模問題的求解效率。

*近似算法：圖模型可以幫助設計近似算法，在保證一定精度的前提下快速求解大規模問題。

實際應用拓展：

二维背包问题的解决在实际应用中有着广泛的前景，例如：

*资源分配：资源有限的情况下，利用二维背包算法可以优化资源分配策略，最大化收益。

*物流规划：在物流运输中，利用二维背包算法可以优化装箱方案，提高空间利用率和运输效率。

*调度优化：在生产调度中，利用二维背包算法可以优化任务分配，缩短工期并提高生产效率。

数据驱动的优化：

随着大数据技术的飞速发展，数据驱动的优化方法在二维背包问题中得到了广泛应用。图论和组合优化可以为数据驱动的优化提供理论基础：

*机器学习：图模型可以作为机器学习模型的输入，辅助决策制定并提升算法性能。

*强化学习：基于图的强化学习算法可以自动调整搜索策略，提高求解效率。

总结：

图论与组合优化在二维背包中的交叉应用有着广阔的前景，可以从复杂问题建模、算法改进、启发式算法设计、大规模问题求解、实际应用拓展和数据驱动的优化等方面促进问题的解决。未来，随着图论、组合优化和计算机科学的不断发展，这一交叉领域的应用将得到进一步拓展和深入。第八部分二维背包问题求解实例关键词关键要点【二维背包问题求解实例】

1.定义问题：二维背包问题是指在给定的两个背包容量和一堆物品的情况下，在每个背包中挑选物品，以最大化物品的总价值。

2.实例描述：假设有5件物品，每件物品具有重量和价值，如下表所示：

|物品|重量|价值|

||||

|A|2|3|

|B|3|4|

|C|4|5|

|D|5|6|

|E|6|7|

背包1的容量为10，背包2的容量为12。

3.求解方法：

-使用动态规划方法，创建一个表格来记录每个子问题的最优解。

-对于背包1和背包2，以及物品1到5，遍历所有可能的组合。

-如果物品的总重量超过背包的容量，则跳过该组合。

-否则，计算当前组合的总价值，并与表格中的现有值进行比较，保留最大值。

-遍历完所有组合后，表格中最后一个元素的值即为二维背包问题的最优解。

【具体求解过程（以表格形式展示）】

背包1容量：10背包2容量：12

||0|1|2|3|4|5|6|7|8|9|10|

|::|::|::|::|::|::|::|::|::|::|::|::|

|0|0|0|0|0|0|0|0|0|0|0|0|

|1|0|3|3|3|3|3|3|3|3|3|3|

|2|0|3|4|7|7|7|7|7|7|7|7|

|3|0|3|4|7|8|11|11|11|11|11|11|

|4|0|3|4|7|8|11|12|15|15|15|15|

|5|0|3|4|7|8|11|12|15|16|19|19|二维背包问题求解实例

在二维背包问题中，给定一个具有n件物品的集合，每件物品有其重量（w1，w2）和价值（v1，v2）。目标是在两个容量分别为（C1，C2）的背包中选择物品，以最大化总价值。

求解步骤：

1.初始化：创建二维数组dp，其中dp[i][j]表示容量为（i，j）的背包中物品的最大总价值。

2.动态规划：对于每件物品i和每个容量组合（j,k），计算以下两个值：

-dp[j+w1][k+w2]：在背包中包含第i件物品的情况。

-dp[j][k]：在背包中不包含第i件物品的情况。

3.选择最大值：对于每个容量组合（j,k），选择具有较大值的dp[j+w1][k+w2]或dp[j][k]。

4.回溯：从dp[C1][C2]开始回溯，确定所选物品。

示例：

考虑以下二维背包问题实例：

|物品|(w1,w2)|(v1,v2)|

||||

|A|(2,3)|(10,12)|

|B|(3,4)|(12,15)|

|C|(4,5)|(15,18)|

|D|(5,6)|(18,21)|

背包容量：C1=7，C2=8

动态规划表：

|k\j|0|1|2|3|4|5|6|7|8|

|||||||||||

|0|0|0|0|0|0|0|0|0|0|

|1|0|0|0|0|0|0|0|10|10|

|2|0|0|0|0|0|0|12|12|22|

|3|0|0|0|0|0|0|15|24|24|

|4|0|