相关疑难解决方法(0)

我在很多地方发现了这个着名的dp问题,但我无法弄清楚如何解决.

您将获得一组n种类型的矩形3-D盒子,其中第i个盒子具有高度h(i),宽度w(i)和深度d(i)(所有实数).你想要创建一个尽可能高的盒子堆叠,但如果下盒子的2-D底座的尺寸都严格大于2的盒子,你只能在另一个盒子的顶部堆叠一个盒子.高架子的D基座.当然,您可以旋转一个框,以便任何一侧作为其基础.也允许使用相同类型的盒子的多个实例.

这个问题对我来说似乎太复杂了.因为它是3D,我得到三个高度,宽度和深度序列.但是因为有可能交换3维,问题对我来说变得更加复杂.所以请有人解释在没有交换时解决问题的步骤,然后在交换时如何解决问题.我对这个问题感到厌倦.所以,请有人解释解决方案的简单方法.

我有一个算法的问题.

给出n个盒子,每个盒子具有固定的重量和强度(均以kg给出).Box的力量告诉我们它能承受的最大重量是多少.我们必须形成最高堆的给定盒子(每个盒子具有相同的高度).您应该提出一种始终给出最优解的算法,这是k盒的最长序列(k <= n).

嗯,这是我已经想到的解决方案:

1. 首先,我们按重量对所有箱子进行分类(最重的是在底部)并形成一堆.
2. 其次,我们按强度排序(最强的是在底部).
3. 然后,对于每个盒子,从底部开始,我们尝试将其拉到底部,只要它的强度能够实现.
4. 最后,我们必须弄清楚必须从顶部移除多少箱子,这导致下面的某些箱子承载的重量超过他们的重量.

看起来这个算法工作得很好,但我不确定它是否总是给出最优解 - 可能它没有.我一直在想动态解决方案,类似于背包问题的解决方案,但我不确定它是否可以通过这种方式解决.对于我的问题,似乎没有最佳的子结构.

预先感谢您的任何帮助.:)