8

我正在研究动态编程，并希望解决以下问题，可以在这里找到http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf：

给你一块长方形布，尺寸为 X 乘 Y，其中 X 和 Y 是正整数，以及可以使用该布制作的 n 个产品的列表。对于 [1,n] 中的每个产品 i，您知道需要一个尺寸为 ai×bi 的矩形布，并且该产品的最终售价为 ci。假设 ai、bi 和 ci 都是正整数。您有一台机器可以将任何矩形布片水平或垂直切成两块。设计一种算法，找到切割 X 乘 Y 块布的最佳策略，以便由所得块制成的产品给出最大的销售价格总和。您可以随意制作任意数量的给定产品副本，如果需要，也可以不制作。（来自 Dasgupta、Papadimitriou 和 Vazirani 的算法。）

似乎我们有一种二维背包问题，但我认为可以通过将权重视为矩形的区域来使用传统的背包算法来解决它。这看起来是一种合理的方法吗？

这是我正在学习的课程的编程作业，因此请仅包含概念讨论和/或伪代码来说明想法。

4

4 回答 4

16

所以你从一个X * Y矩形开始。假设最佳解决方案涉及进行垂直（或水平）切割，那么您有两个新的矩形，其尺寸X * Y1和. 既然你想最大化你的利润，你需要最大化这些新矩形的利润（最优子结构）。因此，您的初始递归如下：对于（水平切割）和（垂直切割）的所有可能值。X * Y2Y1 + Y2 = Yf(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y))X1, X2Y1, Y2

现在的问题是我什么时候真正决定做一个产品？当产品的一个尺寸等于您当前矩形的尺寸之一时，您可以决定制造产品（为什么？因为如果这不成立，并且最佳解决方案包括制造该产品，那么迟早您将需要制造垂直（或水平）切割，这种情况已经在初始递归中处理），因此您进行适当的切割并且您有一个新的矩形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 世界总决赛分享巧克力。

于 2012-09-28T18:39:01.853 回答
3

我认为您应该关注机器将布切成两块的事实。这两个部分中的每一个都可以容纳什么？考虑以下：

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

这四个适合布料，但不能通过三个切割来实现。（可能不同的安排可以让这些特定的作品实现这一点；将其视为概念图，而不是按比例绘制。我今天的 ascii 艺术技能有限。）

专注于“切入点在哪里”应该为您提供动态编程解决方案。祝你好运。

于 2012-09-27T20:08:01.883 回答
2

请在Rect()函数中包含大小矩形(0, something)的必要条件。(something, 0)

于 2012-11-12T21:01:39.057 回答
1

优化（）{

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

}

于 2013-02-25T07:41:41.767 回答