我正在处理一个类似于盒子堆叠问题的问题,这个问题可以用动态规划算法来解决。我在这里读到了关于它的文章,但是我很难理解DP方法,并且希望对它是如何工作的做一些解释。眼前的问题是:
给定X个物体,每个物体都有自己的重量'w‘和强度's',你能在另一个上面叠加多少个?一个物体可以承载它自己的重量和它上面所有重量的总和,只要它不超过它的强度。
我知道它有一个最优的子结构,但它的重叠子问题部分使我感到困惑。我试图创建一个递归树,看看它会在哪里多次计算相同的东西,但是我不知道这个函数是否会接受一个或两个参数。
发布于 2016-12-28 13:29:06
解决这个问题的第一步是证明你可以找到一个最优的堆叠,盒子从最高到最低的强度排序。
然后,您只需按强度对这些框进行排序,并确定哪些框包含在最优堆栈中。
递归子问题有两个参数:使用列表中>= Y位置的方框,找到可以放置在具有X剩余强度的堆栈顶部的最佳堆栈。
发布于 2016-12-28 13:37:37
如果存在良好的DP解决方案,则需要两个params:
要使其工作,您必须找到排序,其中放置对象之上的下一个对象是无用的。也就是说,对于任何违反这个顺序的解决方案,还有另一个解决方案,它遵循这个顺序,并且是更好或更平等的。
您必须证明所选的排序是存在的,并明确定义它。我不认为简单的按强度排序是不够的,因为重量有一定的意义。但这是校对部分..。
https://stackoverflow.com/questions/41361652
复制相似问题