动态规划和背包应用

Question

我正在研究动态编程,我正在寻求解决以下问题,可以在http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf找到:

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

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

这是我正在学习的课程的编程作业,所以请仅包括概念性讨论和/或伪代码来说明想法.

Answer 1

所以你从一个X * Y矩形开始.说最佳的解决方案包括制作垂直(或水平)切割,然后你有大小两个新的矩形X * Y1并X * Y2用Y1 + Y2 = Y.由于您希望最大化您的利润,您需要最大化这些新矩形(最佳子结构)的利润.因此,您的初始递归如下:f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y))对于X1, X2(水平切割)和Y1, 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可能的矩形,对于每一个你尝试每个可能的cut(X + Y)你尝试从这个矩形中制作一个可用的产品.

另外,看看这个类似的问题:2010年ICPC世界总决赛分享巧克力.

Answer 2

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

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

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

专注于“哪里是削减”应该为您提供动态规划解决方案。祝你好运。