动态规划与背包应用

Question

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

您将看到一块尺寸为X x Y的长方形布料，其中X和Y是正整数，以及可以使用该布料制作的n种产品的列表。对于1中的每个产品，n你知道需要一个尺寸为ai * bi的长方形布料，并且产品的最终售价是ci。假设ai、bi和ci都是正整数。你有一台机器，它可以把任何一块长方形的布料水平或垂直地分成两块。设计一个算法，找到裁剪一块X*Y的布料的最佳策略，以便由生成的布料制成的产品提供最大的销售价格总和。您可以随意复制给定产品的任意多个副本，如果需要，也可以不复制。(来自Dasgupta，Papadimitriou和Vazirani的算法。)

看起来我们有一种二维背包问题，但我认为用传统的背包算法通过考虑权重作为矩形的面积来解决它是可能的。这看起来像是一个合理的方法吗？

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

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世界总决赛的巧克力。

Answer 2

我认为你应该关注机器将布料分成两部分这一事实。这两块中的每一块都能装下什么？请考虑以下几点：

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

这四个适合布料，但不是以一种可能通过三次切割实现的方式。(对于这些特定的部分，可能会有不同的安排；将其视为概念图，而不是缩放。今天我的ascii艺术技能有限。)

关注“切入点在哪里”应该会给你提供动态编程解决方案。祝好运。

Answer 3

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