动态规划与背包问题应用

Question

我正在学习动态规划，并且希望解决以下问题，题目可以在这里找到http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf：你有一块长为X、宽为Y的矩形布料和一个由n个产品组成的清单。对于每个产品i（i∈[1,n]），你知道需要一个尺寸为ai×bi的布料，并且该产品的最终售价为ci。假设ai、bi和ci均为正整数。你有一台机器，可以将任何一块矩形布料水平或垂直地切成两块。设计一种算法，以便找到最佳策略，即切割出来的布料制成的产品销售价格之和最大。您可以自由复制任何产品，也可以不复制。（摘自《算法》（Dasgupta，Papadimitriou和Vazirani））。

看起来我们有一种二维背包问题，但我认为可以通过考虑矩形的面积将其仅用传统的背包算法进行解决。这种方法是否合理？

这是我正在学习课程的编程作业，请只包含概念性讨论和/或伪代码以说明思路。

- rmh52

---

一个背包，但是以每个产品区域为单位而不是产品尺寸，你怎么看？ - higuaro

这很像是一个更难的库存切割问题变体，即使在约束编程领域中，它也非常难以解决。让我好好想一想这个问题，因为这一章节都是关于动态规划的，这是一个提示！ - Rafe

Answer 1

首先，您开始是一个 X * Y 矩形。假设最佳解决方案涉及垂直（或水平）切割，则您会得到两个新矩形，其尺寸为 X * Y1 和 X * Y2，其中 Y1 + Y2 = Y。由于您想要最大化收益，所以您需要最大化这些新矩形的收益（最优子结构）。因此，您的初始递归如下：对于所有可能的 X1, X2（水平切割）和 Y1, Y2（垂直切割），f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y))。

现在问题是：我什么时候决定制造产品？当产品的一个维度等于当前矩形的一个维度时，您可以决定制造该产品（为什么？因为如果不成立并且最优解包括制造此产品，则迟早您将需要进行垂直（或水平）切割，而此情况已在初始递归中处理），因此您进行适当的切割，并获得一个新矩形 X * Y1 （或 X1 * Y，具体取决于您制作产品时所做的切割），在这种情况下，递归变为 f(X, Y) = cost of product + f(X1, Y)。

原问题的解是 f(X, Y)。此 DP 解决方案的运行时间将为 O(X * Y * (X + Y + number of available products))：您有 X * Y 个可能的矩形，对于每个矩形，您尝试每个可能的切割（X + Y），并尝试从此矩形中制作一种可用产品。

另外，请查看类似问题：2010 年 ICPC 世界总决赛的 Sharing Chocolate。

- jplot

---

谢谢您的回复。如果您不介意的话，能否提供一些伪代码来说明这个算法将非常有帮助。由于某种原因，我很难想象这个过程。 - rmh52

具体来说，我应该如何检查矩形的最大利润？ - rmh52

Answer 2

我认为你应该关注这个机器将布料切成两块的事实。每个部分可以容纳什么？请考虑以下内容:

+-------------+-------------------+
|             |       Piece B     |
|             |                   |
|  Piece A    +----------+--------+
|             |          |        |
|             |          |        |
|             |          | Piece  |
+-------------+----------+   C    |
|                        |        |
|         Piece D        |        |
+------------------------+--------+

这四个部分可以被放入布料中，但无法通过三个切割实现。（也许以不同的方式排列这些特定的片段可以实现；请将此视为概念图，不按比例绘制。我的ASCII艺术技能今天有限。）

专注于"切在哪里"应该会给你动态规划的解决方案。祝好运。

- rici

Answer 3

请在Rect()函数中包含尺寸为(0，某个值)或(某个值，0)的矩形所需条件。请注意保留HTML标签，但不要提供解释。

- Rahul Kushwaha

Answer 4

优化() {

Rectangle memo[width][height]
optimize(0,0,totalwidth, totalheight, memo)

}

优化（x，y，宽度，高度，备忘录）{

if memo[width][height] != null
    return memo[width][height]

rect = new Rectangle(width, height, value = 0)
for each pattern {

    //find vertical cut solution
    leftVerticalRect = optimize (x, y + pattern.height, pattern.width, height-pattern.height,memo)
    rightVerticalRect = optimize(x  + pattern.width, y, width-pattern.width, height)
    verticalcut = new Cut(x + pattern.width, y, x + pattern.width, y + height)

    //find horizontal cut solution
    topHorizontalRect = optimize ( --parameters-- )
    bottomHortizonalRect = optimize( --parameters--)
    horizontalcut = new Cut( --parameters--)

    //see which solution is more optimal
    if (leftVerticalRect.val + rightVerticalRect.val > topHorizontalRect.val + bottomHorizontalRect.val)
        subprobsolution = vertical cut solution
    else
        subprobsolution = horizontal cut solution

    //see if the solution found is greater than previous solutions to this subproblem
    if (subprobsolution.value + pattern.value > rect.value) {
        rect.subrect1 = subprobsolutionrect1
        rect.subrect2 = subprobsolutionrect2
        rect.pattern = pattern
        rect.cut = subprobsolutioncut
        rect.value = rect.subrect1.value + rect.subrect2.value + rect.pattern.value
    }
}

memo[width][height] = rect
return rect

}

- caitcoo0odes