java - 动态规划与背包应用

Question

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

给你一 block 长方形的布，尺寸为 X×Y，其中 X 和 Y 是正整数，以及可以用这 block 布制作的 n 种产品的列表。对于 [1,n] 中的每个产品 i，您知道需要一 block 尺寸为 ai x bi 的长方形布料，并且该产品的最终售价为 ci。假设ai、bi、ci都是正整数。你有一台机器可以将任何长方形的布水平或垂直切割成两 block 。设计一种算法，找出裁剪 X 乘 Y 的布料的最佳策略，从而使由所得布料制成的产品的售价总和最高。您可以根据需要自由制作任意数量的给定产品副本，也可以根据需要制作任何副本。 (来自 Dasgupta、Papadimitriou 和 Vazirani 的算法。)

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

这是我正在参加的类(class)的编程作业，因此请仅包括概念性讨论和/或伪代码来说明想法。

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) = 产品成本 + f(X1, Y)。

原问题的解是f(X, Y)。此 dp 解决方案的运行时间为 O(X * Y * (X + Y + number of available products)):您有 X * Y 可能的矩形，对于您尝试每一种可能的切割方式 (X + Y)，然后尝试从该矩形中制作出可用的产品之一。

此外，请查看这个类似的问题:Sharing Chocolate 来自 2010 年 ICPC 世界总 final 。