对象堆栈，动态编程

我正在处理一个类似于可以用动态编程算法解决的盒子堆叠问题的问题。我在这里阅读了关于它的帖子，但是我很难理解DP方法，并且希望对它的工作原理做一些解释。下面是手头的问题：对象堆栈，动态编程

鉴于X对象，每个都有自己的权重“W”和强度的“，你怎么许多可堆叠在彼此的顶部？一个物体可以携带它自己的重量和其上的所有重量的总和，只要它不超过其强度。

据我所知，它有一个最佳的子结构，但它的重叠子问题部分让我困惑。我试图创建一个递归树来查看它会多次计算相同的东西，但我无法弄清楚函数是否需要一个或两个参数。

2016-12-28 ALEXANDER WORMBS

我认为这个问题属于http://cs.stackexchange.com/。 – user28434

你能指出这个问题的根源吗（提供[适当的归属]（http://cs.stackexchange.com/help/referencing）来源）？你能链接到你指的SO帖子，并告诉我们你的具体困惑是什么？另外，你有什么尝试？您可能想参考我们的[关于动态编程的参考资料]（http://stackoverflow.com/tags/dynamic-programming/info），然后告诉我们您取得了哪些进展。你尝试过哪些子问题？ –

交叉发表：http://cs.stackexchange.com/q/68049/755，http://stackoverflow.com/q/41361652/781723。请[不要在多个网站上发布相同的问题]（http://meta.stackexchange.com/q/64068）。每个社区都应该诚实地回答问题，不要浪费任何人的时间。 @ user28434，如果你要推荐另一个网站，请告知人们不要交叉发帖（否则会留下不好的经历）。如果他们认为在其他地方更合适，您可以建议他们删除他们的问题并将其发布到别处。 –

解决此问题的第一步是证明您可以找到具有从最高到最低强度排序的框的最佳堆栈。

然后，您只需按强度对盒子进行排序并找出哪些盒子包含在最佳堆栈中。

递归子问题有两个参数：使用列表中的位置> = Y处的方框，找到堆放在堆栈顶部并使用X剩余强度的最佳堆栈。

来源

2016-12-28 13:29:06

如果良好的DP解决方案存在，它需要2个PARAMS：

数
未访问对象的总重量目前可以负担得起（重量走访对象不要紧访问对象或未访问的对象的数量）

为了使它工作，你必须找到排序，在下一个对象的顶部放置对象是没有用的。也就是说，对于任何违反此顺序的解决方案，都有另一种解决方案遵循此顺序并且更好或相等。

您必须证明选定的排序存在并明确定义它。我不认为按照马特蒂莫曼斯的建议通过力量进行简单的排序就足够了，因为体重有一定的意义。但它的打样部分...

来源

2016-12-28 13:37:37

对象堆栈，动态编程

回答

相关问题