动态规划和背包的应用 [英] Dynamic Programming and Knapsack Application
问题描述
林学习动态规划，我期待解决以下的问题，可以在这里<一个发现href="http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf">http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:
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:
正在给定的矩形一块布有尺寸x除以Y，其中X和Y是正整数，和n个产品，可以使用布进行的列表。对于每个产品i的[1，n]的你知道的尺寸布的矩形的AI通过双向是必要的，该产品的最终销售价格是词。假设AI，BI和CI均为正整数。你有一台机器，可切割任意一块长方形的布成两片水平或垂直。设计了一种算法，找到了针对由布ÿ片切割的X，以便从所得的片制成的产品得到的销售价格的最大总和的最佳策略。你可以自由如果需要的话，使你的愿望给定产品，或者没有多份。 （从算法由达斯古普塔，PAPADIMITRIOU和瓦齐拉尼。）
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.)
看来，我们有一种2维背包问题，但我想它可能只是解决它与传统的背包算法考虑的权重为矩形的面积。这看起来像一个合理的做法？
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?
这是一个编程任务的过程中，我采取所以请只包括概念性的讨论和/或伪code来说明观点。
This is a programming assignment for a course I'm taking so please only include conceptual discussion and/or pseudo-code to illustrate ideas.
推荐答案
所以，你开始用 X * Y 矩形。再说了最佳的解决方案包括制造垂直（或水平）切割，那么你有两个新的矩形，尺寸 X * Y 1 和 X * Y 2 与 Y1 + Y2 = Y 。既然你想最大化你的利润，你需要最大限度地发挥这些新矩形的利润（最优子的）。所以，你最初的递归的情况如下： F（X，Y）= MAX（F（X，Y）+ F（X，Y2），F（X，Y）+ F（X，Y） ）为 X1的一切更多钞票值，X2 （横剪）和 Y1，Y2 （垂直切割）。
So you start with a X * Y rectangle. Say the optimal solution involves making a vertical (or horizontal) cut, then you have two new rectangles with dimensions X * Y1 and X * Y2 with 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 1 （或 X1 * Y ），这取决于对砍你作出获得产品），在此情况下，递归变成 F（X，Y）=产物+ F的成本（X 1，Y）的
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).
原问题的解决方案是 F（X，Y）。该DP解决方案的运行时间将是 O（X * Y *可用产品（X + Y +编号））：你有 X *是可能的矩形，对于每一种尝试一切可能的切口（ X + 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 * Y possible 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.
另外，看看这个类似的问题：共享巧克力的从2010 ICPC全球总决赛
Also, check out this similar problem: Sharing Chocolate from the 2010 ICPC World Finals.
这篇关于动态规划和背包的应用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
