动态规划与背包应用 [英] Dynamic Programming and Knapsack Application

问题描述

我正在研究动态规划，并希望解决以下问题，可以在这里找到 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.

这篇关于动态规划与背包应用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！