java - 是否有计算组件净需求的最佳算法？

Question

假设我有一个元素 list ，例如 5 张 table 、5 把椅子等。每张 table 由 4 条腿和一个桌面组成。每条腿由2 block 木头组成，桌面由5 block 木头和4个螺丝等组成。

我将项目组件列表存储在包含列(项目 1、项目 2、数量)的数据库中，其中项目 2 是项目 1 的组件，“数量”是所需的项目 2 的数量。

我想计算最低级别 Material 列表的总净需求，而不假设层次结构级别的数量，是否有最佳方法来执行此操作？

如果重要的话，我打算用 Java 来做。

Answer 1

您实际上已经描述了您的解决方案!

您可以做的是创建一棵树。实际上是几棵树，因为您提到椅子和 table 将是单独的树。

该节点应该包含 item1，它的子节点应该是它的每一个组件，以及它需要多少组件的计数。所以，你会有一个 child 列表，即 (Wood, 2) (Nail, 4)

当您创建节点时，将它们添加到 map 中，这样您就可以轻松地跟踪项目是否已创建，以便您可以使用相同的项目。没有父节点的节点应始终添加到树列表中。应从树列表中删除具有父节点的节点(树根是此定义中的顶级组件)。

填充树时，请使用上述信息。没有 parent =新树。然后检查它是否使用任何树来构建其组件。如果是，则从树列表中删除该树。

假设我们有 Leg Chair Tabletop ChairTop Desk

我们将添加 Leg 作为根。它里面有 child 木头和钉子，这是我们创造的。

然后我们将添加使用 Leg 的 Chair，因此我们从 Trees 列表中删除 Leg 并将其添加到 Chair，然后将 Chair 添加到 Trees 列表。

TableTop 是由木头制成的，因此我们采用 Wood 节点并将其添加为子节点，但 TableTop 和 Chair 不相关，因此 TableTop 现在是一棵新树。

ChairTop 是 Chair 的一部分，因此我们将它作为 Chair 的子项添加，并且它的部分(如果不是木头)将作为节点添加。

Desk 由 TableTop 组成，因此它成为根，而 TableTop 不再是树的根。

最终结果是像树一样的 table 和椅子； TableTop、ChairTop、Leg 作为节点；木头和其他任何东西作为叶节点。

所有树的最低级 Material 是基本组件。

完成后，您可以编写一个方法，基本上遍历子项并传回一个项目/计数列表，将所有内容正确相乘。