给定三维空间中的
如何使用动态规划和贪心算法来实现呢？
n 个盒子，其尺寸分别为 (h, w, d)。目标是将它们叠放在一起，以获得最大高度（可以旋转盒子）。每一个被放置在上面的盒子都应该要比下面的盒子小（w, d 小）。如何使用动态规划和贪心算法来实现呢？
箱子堆放问题
3
- mozhdeh
8
2就目前这个问题而言，它似乎更多地涉及算法而非 C++ 的一般性质。 - Flexo
1不确定“较小的尺寸（w，d）”是什么意思。您是指顶部的表面积应该比底部小吗？还是说您的意思是可以安排侧面，使底部完全覆盖顶部（是否有数学术语可描述此情况）？例如，2x2的表面积比3x1大，但前者仍然无法完全覆盖后者（据我所知）。 - Johannes Schaub - litb
这似乎是一道作业题，而且很难。但这肯定是一种背包问题的形式。http://en.wikipedia.org/wiki/Knapsack_problem - madmik3
1这是 https://dev59.com/MHE95IYBdhLWcg3wY9D6 的副本。 - Daniel Trebbien
2@madmik3：这根本不是背包问题。看起来更像是块叠放问题，但我不确定。 - DReJ
显示剩余3条评论
1个回答
4
- IVlad
7
很棒的视频。但是由于算法要求您克隆所有盒子，如果输入只有一个1x2x3的盒子，该算法会使用2个盒子找到高度为4的塔。我想知道这是否是mozhdeh的意图。 - Jason Orendorff
@Jason Orendorff - 即使这不是 OP 想要的，我认为通过在尝试放置盒子时考虑旋转，而不是克隆盒子，可以防止发生这种情况。或者通过克隆并为每个盒子分配一个 ID，确保每个盒子只使用一次。 - IVlad
我认为这是最长递增子序列问题，但我不确定。 - mozhdeh
我不知道如何在图论中解决它。什么是最好的贪心算法？ - mozhdeh
@IVlad 我在 https://dev59.com/MHE95IYBdhLWcg3wY9D6#2329685 上留了一条评论，解释了为什么我认为那个方法行不通。尽管有很多得票数很高的答案，但我还没有看到一个比指数级更好的算法... - Jason Orendorff
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接