小编Rob*_*ski的帖子

我有一个算法的问题.

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

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

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

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

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