动态规划和背包应用
我正在研究动态编程，并希望解决以下问题，可以在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的算法。）
看起来我们有一种二维背包问题，但我认为通过将权重视为矩形区域，可以用传统的背包算法解决它。 这看起来像是一种合理的方法吗？
这是我正在学习的课程的编程作业，所以请仅包括概念性讨论和/或伪代码来说明想法。
所以你从一个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可能的矩形，对于每一个你尝试每个可能的切割（ X + Y ）和你试图从这个矩形中制作一个可用的产品。
另外，看看这个类似的问题：2010年ICPC世界总决赛分享巧克力 。
请在Rect（）函数中包含size (0, something)或(something, 0)矩形的必要条件。
我认为你应该把重点放在机器将布料切成两块的事实上。 什么能适合这两件？ 考虑以下：
+-------------+-------------------+ | | Piece B | | | | | Piece A +----------+--------+ | | | | | | | | | | | Piece | +-------------+----------+ C | | | | | Piece D | | +------------------------+--------+
这四个适合布料，但不能以三种切割方式实现。 （可能不同的安排会允许使用这些特定的部分;将其视为概念图，而不是扩展。我的ascii艺术技能今天有限。）
专注于“切割的位置”应该为您提供动态编程解决方案。 祝你好运。
optimize（）{
Rectangle memo[width][height] optimize(0,0,totalwidth, totalheight, memo)
}
optimize（x，y，width，height，memo）{
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
}