Dinamik Programlama ve Sırt Çantası Uygulaması

Question

Im ve burada http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf bulunabilir aşağıdaki sorunu çözmek için arıyorum pozitif tamsayılar ve bez kullanılarak yapılabilecek n ürünlerin bir listesidir. [1, n] 'deki her bir ürün için, bie boyutuna göre bir dikdörtgen kumaşın gerekli olduğunu ve ürünün nihai satış fiyatının ci olduğunu biliyorsunuzdur. Ai, bi ve ci'nin pozitif tam sayı olduğunu varsayalım. Dikdörtgen bir kumaş parçasını yatay veya dikey olarak iki parçaya ayırabilen bir makineniz var. Bir X parçasını Y parçasını bezle kesmek için en iyi stratejiyi bulan bir algoritma tasarlayın, böylece elde edilen parçalardan üretilen ürünler maksimum satış fiyatları toplamını verir. Belirli bir ürünün istediğiniz kadar kopyalarını veya istediğiniz takdirde hiçbirini yapmakta özgürsünüz. (Dasgupta, Papadimitriou ve Vazirani'den Algoritmalardan.)

Bir çeşit 2 boyutlu sırt çantası problemimiz var gibi gözüküyor, ama sanırım bunu geleneksel sırt çantası algoritmasıyla çözmeyi düşünebilirim. Dikdörtgenlerin alanları olarak ağırlıklar. Bu makul bir yaklaşım gibi görünüyor mu?

Bu, benim aldığım bir ders için bir programlama ödevidir, sadece fikirleri göstermek için sadece kavramsal tartışmayı ve/veya sözde kodu dahil edin.

Answer 1

Makinenin kumaşı iki parçaya böldüğü gerçeğine odaklanmalısınız. Bu iki parçanın her birine ne sığdırabilir? Aşağıdaki düşünün:

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

kumaşa Bu dört fit değil üç kesim ile elde etmek mümkündür şekilde. (Muhtemelen farklı bir düzenleme, bu özel parçalarla buna izin verir; kavramsal bir diyagram olarak düşünün, ölçeklememeliyim. Benim ascii sanat becerilerim bugün sınırlıdır.)

"Kesim nerede" size odaklanmalıdır. dinamik programlama çözümü. İyi şanslar.

Answer 2

X * Y dikdörtgeni ile başlarsınız. En uygun çözümün dikey (veya yatay) bir kesim yapılmasını içerdiğini, sonra X * Y1 ve X * Y2 boyutlarında iki yeni dikdörtgenin Y1 + Y2 = Y ile olduğunu söyleyin. Kârınızı en üst düzeye çıkarmak istediğinizden, bu yeni dikdörtgenlerdeki karı en üst düzeye çıkarmanız gerekir (en uygun alt yapı). Böylece, ilk yinelemeniz şu şekilde olur: X1, X2 (yatay kesim) ve Y1, Y2 (dikey kesim) tüm olası değerleri için f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y)).

Şimdi soru şu: Gerçekten ne zaman ürün yapmaya karar verdim? Boyutlarından biri geçerli dikdörtgenizin boyutlarından birine eşit olduğunda bir ürün oluşturmaya karar verebilirsiniz (Bu neden olmazsa ve en uygun çözüm bu ürünü oluşturmayı içerirse, o zaman er ya da geç gerekir) dikey (veya yatay) bir kesim yapmak ve bu durum zaten başlangıç ​​yinelemesinde ele alınır), böylece uygun kesim yaparsınız ve ürünü elde etmek için yaptığınız kesime bağlı olarak X * Y1 (veya X1 * Y) yeni bir dikdörtgene sahip olursunuz, Bu durumda özyineleme f(X, Y) = cost of product + f(X1, Y) olur.

Özgün sorunun çözümü f(X, Y) şeklindedir. Bu dp çözümünün çalışma süresi O(X * Y * (X + Y + number of available products)) olacaktır: X * Y olası dikdörtgenler vardır, bunlardan her olası kesim için deneyin (X + Y) ve bu dikdörtgenin dışındaki kullanılabilir ürünlerden birini yapmaya çalışın.Ayrıca, bu benzer soruna bir bakın: 2010 ICPC World Finals'ten Chocolate'i Paylaşımı.

Answer 3

Lütfen veya (something, 0) boyutlarındaki dikdörtgen için gerekli koşulları Rect() işlevine dahil edin.

Answer 4

optimize() {

Rectangle memo[width][height] 
optimize(0,0,totalwidth, totalheight, memo) 

}

optimize (x, y, en, yükseklik, not) {

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 

}