当前位置: 首页 > 知识库问答 >
问题:

对象堆叠,动态规划

耿玄裳
2023-03-14

我正在处理一个类似于可以用动态编程算法解决的盒子堆叠问题的问题。我在SO上阅读了有关它的帖子,但是我很难理解DP方法,并希望对其工作原理进行一些解释。这是手头的问题:

给定X个物体,每个都有自己的重量“w”和强度“s”,你能把多少个叠在一起?一个物体只要不超过它的强度,就可以承受它自身的重量和它上面所有重量的总和。

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

共有2个答案

蔡鸿骞
2023-03-14

如果存在良好的 DP 解决方案,则需要 2 个参数:

  • 已访问对象的数量或未访问对象的数量
  • 您当前可以负担的未访问对象的总重量(访问对象的重量无关紧要)

为了让它工作,你必须找到排序,在这种情况下,把一个对象放在下一个对象上面是没有用的。也就是说,对于任何违反这一顺序的解决方案,在这一顺序之后都有另一个更好或相等的解决方案。

你必须证明所选排序的存在并明确定义它。我不认为马特·蒂默曼斯建议的简单的按强度排序就足够了,因为权重有一些意义。但这是打样部分…

苏边浩
2023-03-14

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

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

递归子问题有两个参数:找到可以放在剩余强度为 X 的堆栈顶部的最佳堆栈,使用位置的框

 类似资料:
  • 指定在堆叠顺序中的哪个位置添加新对象 Illustrator 从第一个对象开始顺序堆积所绘制的对象。对象的堆叠方式将决定其重叠时如何显示。可以随时使用 “图层 ”面板或 “对象 ”>“排列 ”命令更改图稿中对象的堆叠顺序(也被称为绘画顺序)。 ❖在 “图层 ”面板中执行下列任一操作: 要在哪个对象上添加新对象,请单击此对象名称。 若要在图层或组的顶部添加新对象,请单击图层或组名称。 在 Windo

  • 指定在堆叠顺序中的哪个位置添加新对象 Illustrator 从第一个对象开始顺序堆积所绘制的对象。 对象的堆叠方式将决定其重叠时如何显示。对象的堆叠顺序取决于您使用的绘图模式。在正常绘图模式下创建新图层时,新图层将放置在现用图层的正上方,且任何新对象都在现用图层的上方绘制出来。但是,在背面绘图模式下创建新图层时,新图层将放置在现用图层的正下方,且任何新对象都在选定对象的下方绘制出来(如果未选中任

  • 我无法弄清楚重叠子问题的DP第一属性在哪里适合子集和问题。然而,我理解最优子结构部分。在执行包含和排除元素的递归解决方案时,问题在哪里重叠 是不是因为这是一个NP问题,所以没有DP的两个性质 问题的链接是http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ 有人能帮助我理解这一点吗。

  • 问题链接如下: https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ 我没有看到重叠的子问题属性在问题中得到满足,至少在输入情况下是如此。例如,在下面的链接中,递归树没有任何重叠的子问题 http://www.zrzahid.com/subset-sum-problem-dynamic-programming/

  • 我想要一张堆叠的条形图,那里有一条阈值线。阈值线以上的条色应为红色,阈值线以下的条色应为绿色。问题是,阈值不是恒定的,对于每个x值,它可能有不同的值。我想随时更新这个阈值,以获得某个x值。如何做到这一点?很明显,柱状图的y参数应该是动态的,也许我应该为它们传递一个函数?请帮我做这个。我也认为阈值应该是一个函数,因为我会更新它

  • 柱形图和面积图可以设置成堆叠的形式,堆叠后同一个分类下的数据不再是水平依次排列而是依次从上到下堆叠在一起。 堆叠有两种形式,普通的堆叠和按百分比堆叠;普通堆叠是按照数值大小依次堆叠,百分比堆叠是按照数值所占百分比进行堆叠。 下面是堆叠图和百分比堆叠图例子: 图 5-1 堆叠图 图 5-2 百分比堆叠图 通过指定柱形图或面积图的 stacking 属性即可是图形堆叠,示例代码如下: plotOpit