8

私は動的プログラミングを勉強しており、次の問題を解決しようとしています。

X と Y の寸法 (X と Y は正の整数) の長方形の布と、その布を使用して作成できる n 個の製品のリストが与えられます。[1,n] の各製品 i について、寸法 ai x bi の布の長方形が必要であり、製品の最終販売価格が ci であることを知っています。ai、bi、および ci はすべて正の整数であると仮定します。長方形の布を縦または横に 2 つに切断できる機械があります。X x Y の布を裁断して得られる布から作られた製品の販売価格の合計が最大になるように、布を裁断するための最適な戦略を見つけるアルゴリズムを設計します。特定の製品のコピーを好きなだけ自由に作成できます。必要に応じてコピーを作成することもできません。(Dasgupta、Papadimitriou、および Vazirani による Algorithms から。)

2 次元のナップザック問題のようなものがあるようですが、重みを長方形の面積と見なすことで、従来のナップザック アルゴリズムで解決できるのではないかと考えています。これは合理的なアプローチのように思えますか?

これは私が受講しているコースのプログラミング課題です。概念的な議論やアイデアを説明するための疑似コードのみを含めてください。

4

4 に答える 4

16

したがって、X * Y長方形から始めます。最適な解決策が垂直 (または水平) カットを作成することであるとすると、寸法X * Y1とX * Y2を持つ 2 つの新しい長方形ができますY1 + Y2 = Y。利益を最大化したいので、これらの新しい四角形 (最適部分構造) で利益を最大化する必要があります。したがって、最初の再帰は次のようになります: (水平カット) と(垂直カット)f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y))のすべての可能な値。X1, X2Y1, Y2

問題は、実際に製品を作ることをいつ決定するかということです。寸法の 1 つが現在の長方形の寸法の 1 つに等しい場合、製品を作成することを決定できます (なぜですか? これが成り立たず、最適な解決策にこの製品の作成が含まれる場合、遅かれ早かれ、作成する必要があるからです)。垂直 (または水平) カットで、このケースは最初の再帰で既に処理されているため)、適切なカットを行うと、新しい長方形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) を試し、この長方形から利用可能な製品の 1 つを作成しようとします。

また、この同様の問題をチェックしてください: 2010 ICPC World Finals からのチョコレートの共有。

于 2012-09-28T18:39:01.853 に答える
3

機械が布を2つに切ることに注目すべきだと思います。これらの 2 つのピースのそれぞれに何が収まりますか? 次の点を考慮してください。

+-------------+-------------------+
|             |       Piece B     |
|             |                   |
|  Piece A    +----------+--------+
|             |          |        |
|             |          |        |
|             |          | Piece  |
+-------------+----------+   C    |
|                        |        |
|         Piece D        |        |
+------------------------+--------+

これらの 4 つは布に収まりますが、3 つのカットで達成できる方法ではありません。（おそらく、これらの特定の作品では、別の配置でそれが可能になるでしょう。これは縮尺ではなく、概念図と考えてください。現在、私のアスキー アートのスキルは限られています。）

「カットはどこにあるか」に焦点を当てると、動的プログラミングのソリューションが得られるはずです。幸運を。

于 2012-09-27T20:08:01.883 に答える
2

(0, something)サイズの長方形またはRect（）関数(something, 0)に必要な条件を含めてください。

于 2012-11-12T21:01:39.057 に答える
1

最適化（） {

Rectangle memo[width][height]
optimize(0,0,totalwidth, totalheight, 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

}

于 2013-02-25T07:41:41.767 に答える