問題描述
我正在研究動態規劃，并希望解決以下問題，可以在這里找到 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 個產品的列表.對于 [1,n] 中的每個產品 i，您知道需要一個尺寸為 ai×bi 的矩形布，并且該產品的最終售價為 ci.假設 ai、bi 和 ci 都是正整數.您有一臺機器可以將任何矩形布片水平或垂直切成兩塊.設計一種算法，找到切割 X 乘 Y 塊布的最佳策略，以便由所得塊制成的產品給出最大的銷售價格總和.您可以隨意制作任意數量的給定產品副本，如果需要，也可以不制作.(摘自 Dasgupta、Papadimitriou 和 Vazirani 的算法.)
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.)
似乎我們有一種二維背包問題，但我認為可以通過將權重視為矩形的面積來使用傳統的背包算法來解決它.這看起來是一種合理的方法嗎?
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.
推薦答案
所以你從一個 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(垂直切割)的所有可能值.
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 * Y1(或 X1 * Y)，具體取決于您為獲得產品所做的切割)，在這種情況下，遞歸變為 f(X, Y) = 產品成本 + f(X1, 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 + number of available products)):您有 X * Y 可能的矩形，例如每一個你都嘗試了所有可能的切割 (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.
另外，看看這個類似的問題:Sharing Chocolate from the 2010 ICPC World Finals.
Also, check out this similar problem: Sharing Chocolate from the 2010 ICPC World Finals.
這篇關于動態規劃與背包應用的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！