首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >对象堆叠,动态规划

问对象堆叠,动态规划
EN

Stack Overflow用户
提问于 2016-12-28 11:57:52
回答 2查看 736关注 0票数 0

我正在处理一个类似于盒子堆叠问题的问题,这个问题可以用动态规划算法来解决。我在这里读到了关于它的文章,但是我很难理解DP方法,并且希望对它是如何工作的做一些解释。眼前的问题是:

给定X个物体,每个物体都有自己的重量'w‘和强度's',你能在另一个上面叠加多少个?一个物体可以承载它自己的重量和它上面所有重量的总和,只要它不超过它的强度。

我知道它有一个最优的子结构,但它的重叠子问题部分使我感到困惑。我试图创建一个递归树,看看它会在哪里多次计算相同的东西,但是我不知道这个函数是否会接受一个或两个参数。

EN

回答 2

Stack Overflow用户

发布于 2016-12-28 13:29:06

解决这个问题的第一步是证明你可以找到一个最优的堆叠,盒子从最高到最低的强度排序。

然后,您只需按强度对这些框进行排序,并确定哪些框包含在最优堆栈中。

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

票数 2
EN

Stack Overflow用户

发布于 2016-12-28 13:37:37

如果存在良好的DP解决方案,则需要两个params:

  • 访问对象的数量或未访问对象的数量
  • 您目前负担得起的未访问对象的总重量(访问对象的重量并不重要)

要使其工作,您必须找到排序,其中放置对象之上的下一个对象是无用的。也就是说,对于任何违反这个顺序的解决方案,还有另一个解决方案,它遵循这个顺序,并且是更好或更平等的。

您必须证明所选的排序是存在的,并明确定义它。我不认为简单的按强度排序是不够的,因为重量有一定的意义。但这是校对部分..。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/41361652

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档