C++ 盒子堆叠问题

箱子堆叠问题 也被称为动态规划挑战。它要求用户确定可以堆叠在一起的最高箱子堆。一个箱子只有在其底面积较小的情况下才能堆叠在另一个箱子之上，而且即使那样，也只有在箱子旋转后才能进行堆叠。

1. 问题表述： 给定一系列箱子及其尺寸（长、宽和高），目标是确定在遵守限制的情况下，通过堆叠箱子可以达到的最高高度。
2. 生成旋转： 有必要为每个箱子创建所有可能的旋转以处理箱子的旋转。因此，在堆叠时，我们可以考虑不同的箱子方向。每个箱子的三种可能旋转允许各种堆叠配置。
3. 基于动态规划的方法： 此方法用于确定可以达到的最高高度。通过建立一个状态来解决问题，该状态表示在考虑当前位于顶部的箱子时可以达到的最高高度。在检查给定箱子下方的所有箱子时，我们记录了每个箱子可能达到的最高高度。在动态规划状态转换期间，当前箱子与下方所有箱子进行比较，然后相应地更新最大高度。
4. 算法实现： 该过程通常使用数据结构（例如向量或数组）组合来实现，以记录箱子尺寸和动态规划数组，后者用于跟踪可能达到的最高高度。该方法遍历箱子并确定在考虑到问题施加的限制下可以达到的最高点。
5. 输出和分析： 算法处理完所有箱子后，它提供通过堆叠箱子可以达到的最高高度。该输出代表了给定箱子集的箱子堆叠问题的解决方案。
6. 基于底面积的排序： 在创建所有旋转后，箱子根据其底面积以非递增方式排列。这种排序方法确保底面积较小的箱子只能堆叠在底面积较大的箱子之上。

编码

我们举一个例子来说明 C++ 中的箱子堆叠问题

输出

Input List elements are
4 7 6
1 3 2
4 6 5
10 32 12
Sorted List elements are
10 32 12 
12 32 10 
32 10 12 
4 7 6 
4 6 5 
6 7 4 
7 4 6 
5 6 4 
6 4 5 
1 3 2 
2 3 1 
3 1 2 
Max height is 60
Output list elements are 
{3,2,1}
{1,2,3}
{6,5,4}
{4,5,6}
{4,6,7}
{32,12,10}
{10,12,32}

使用共享指针和唯一类来解决箱子堆叠问题。它包括一个管理箱子堆叠过程的 Box_Stacking 类和一个表示箱子尺寸的dim_ension 结构。该方法使用动态规划在根据底面积对箱子进行排序后确定可能达到的最高箱子堆叠高度。还准备了构成最大高度的箱子输出列表。main 方法生成最大高度以及构成它的箱子列表，并使用一系列示例箱子来展示如何使用Box_Stacking类。