java 动态规划和背包应用
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12626854/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Dynamic Programming and Knapsack Application
提问by rmh52
Im studying dynamic programming and am looking to solve the following problem, which can be found here http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:
我正在学习动态规划并希望解决以下问题，可以在这里找到http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf：
You are given a rectangular piece of cloth with dimensions X by Y, where X and Y are positive integers, and a list of n products that can be made using the cloth. For each product i in [1,n] you know that a rectangle of cloth of dimensions ai by bi is needed and that the final selling price of the product is ci. Assume that ai, bi, and ci are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that finds the best strategy for cutting an X by Y piece of cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none if desired. (From Algorithms by Dasgupta, Papadimitriou, and Vazirani.)
给定一块长方形的布，其尺寸为 X x Y，其中 X 和 Y 是正整数，以及可以使用该布制成的 n 个产品的列表。对于 [1,n] 中的每个产品 i，您知道需要一块尺寸为 ai x bi 的矩形布，并且该产品的最终售价为 ci。假设ai、bi 和ci 都是正整数。您有一台机器可以将任何矩形布块水平或垂直地切成两块。设计一种算法，找出将 X 乘 Y 一块布切割的最佳策略，以便由所得布块制成的产品给出最大的销售价格总和。您可以随心所欲地制作任意数量的给定产品的副本，或者根据需要不制作任何副本。（来自 Dasgupta、Papadimitriou 和 Vazirani 的算法。）
It seems we have a sort of 2-dimensional knapsack problem, but I'm thinking it may be possible to just solve it with the traditional knapsack algorithm by considering the weights as the areas of the rectangles. Does this seem like a reasonable approach?
看起来我们有一种二维背包问题，但我认为可以通过将权重视为矩形的面积来使用传统的背包算法来解决它。这看起来是一个合理的方法吗？
This is a programming assignment for a course I'm taking so please only include conceptual discussion and/or pseudo-code to illustrate ideas.
这是我正在学习的一门课程的编程作业，因此请仅包含概念性讨论和/或伪代码来说明想法。
回答by jplot
So you start with a X * Yrectangle. Say the optimal solution involves making a vertical (or horizontal) cut, then you have two new rectangles with dimensions X * Y1and X * Y2with Y1 + Y2 = Y. Since you want to maximize your profit, you need to maximize the profit on these new rectangles (optimal substructure). So your initial recursion goes as follows: f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y))for all posible values of X1, X2(horizontal cut) and Y1, Y2(vertical cut).
所以你从一个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（垂直切割）的所有可能值。
Now the question is when do I actually decide to make a product ?You can decide to make a product when one of its dimensions equals one of the dimensions of your current rectangle (why ? Because if this doesn't hold, and the optimal solution includes making this product, then sooner or later you will need to make a vertical (or horizontal) cut and this case is already handled in the initial recursion), so you make the appropriate cut and you have a new rectangle X * Y1(or X1 * Y), depending on the cut you made to obtain the product), in this case the recursion becomes f(X, Y) = cost of product + f(X1, Y).
现在的问题是我什么时候真正决定做一个产品？当其中一个尺寸等于当前矩形的一个尺寸时，您可以决定制作产品（为什么？因为如果这不成立，并且最佳解决方案包括制作此产品，那么迟早您将需要制作垂直（或水平）切割，这种情况已经在初始递归中处理过），因此您进行了适当的切割，并且您有一个新的矩形X * Y1（或X1 * Y），具体取决于您为获得产品所做的切割），在这种情况下递归变成f(X, Y) = cost of product + f(X1, Y).
The solution of the original problem is f(X, Y). The running time of this dp solution would be O(X * Y * (X + Y + number of available products)): you have X * Ypossible rectangles, for each of these you try every possible cut (X + Y) and you try to make one of the available products out of this rectangle.
原问题的解是f(X, Y)。此 dp 解决方案的运行时间将是O(X * Y * (X + Y + number of available products))：您有X * Y可能的矩形，对于每个矩形，您尝试所有可能的切割 ( X + Y) 并尝试从该矩形中制作可用产品之一。
Also, check out this similar problem: Sharing Chocolatefrom the 2010 ICPC World Finals.
另外，看看这个类似的问题：分享2010 年 ICPC 世界总决赛的巧克力。
回答by rici
I think you should focus on the fact that the machine cuts the cloth into two pieces. What can fit in each of those two pieces? Consider the following:
我认为您应该关注机器将布切成两块这一事实。这两个部分中的每一个都可以放入什么？考虑以下：
+-------------+-------------------+
| | Piece B |
| | |
| Piece A +----------+--------+
| | | |
| | | |
| | | Piece |
+-------------+----------+ C |
| | |
| Piece D | |
+------------------------+--------+
These four fit in the cloth, but not in a way that's possible to achieve with three cuts. (Possibly a different arrangement would allow that with these particular pieces; think of this as a conceptual diagram, not to scale. My ascii art skills are limited today.)
这四个适合布料，但无法通过三个切割来实现。（对于这些特定的作品，可能会有不同的安排；将其视为概念图，而不是按比例绘制。我今天的 ascii 艺术技能有限。）
Focussing on "where is the cut" should give you the dynamic programming solution. Good luck.
专注于“削减在哪里”应该会给你动态规划解决方案。祝你好运。
回答by Rahul Kushwaha
Please include the necessary conditions for rectangle of size (0, something)or (something, 0)in the Rect()function.
请在矩形的大小(0, something)或(something, 0)在Rect()函数中包含必要的条件。
回答by caitcoo0odes
optimize() {
优化（）{
Rectangle memo[width][height]
optimize(0,0,totalwidth, totalheight, memo)
}
}
optimize(x, y, width, height, 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
}
}
