गतिशील प्रोग्रामिंग और बस्ता आवेदन

Question

इम गतिशील प्रोग्रामिंग का अध्ययन और निम्न समस्या, यहां पाया जा सकता है जो http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf हल करने के लिए देख रहा हूँ:

आप वाई, जहां एक्स और वाई द्वारा आयाम एक्स के साथ कपड़े का एक आयताकार टुकड़ा दिया जाता है सकारात्मक पूर्णांक हैं, और एन उत्पादों की एक सूची जिसे कपड़े का उपयोग करके बनाया जा सकता है। प्रत्येक उत्पाद के लिए मैं [1, एन] में जानता हूं कि द्विपक्षीय आयामों के कपड़ा के आयत की आवश्यकता है और उत्पाद की अंतिम बिक्री मूल्य सीआई है। मान लें कि एआई, द्वि और सीआई सभी सकारात्मक पूर्णांक हैं। आपके पास एक मशीन है जो किसी भी आयताकार टुकड़े को दो टुकड़ों में क्षैतिज या लंबवत रूप से काट सकती है। एक एल्गोरिदम डिज़ाइन करें जो कप के वाई टुकड़े द्वारा एक्स को काटने के लिए सबसे अच्छी रणनीति पाता है ताकि परिणामी टुकड़ों से बने उत्पाद अधिकतम बिक्री मूल्यों को दे सकें। आप किसी दिए गए उत्पाद की जितनी चाहें उतनी प्रतियां बनाने के लिए स्वतंत्र हैं, या वांछित होने पर कोई भी नहीं। (दासगुप्त, पापदीमित्रियो और वजीरानी द्वारा एल्गोरिदम से।)

ऐसा लगता है कि हमारे पास 2-आयामी नापसंद समस्या है, लेकिन मुझे लगता है कि इसे पारंपरिक knapsack एल्गोरिदम के साथ हल करना संभव हो सकता है आयत के क्षेत्रों के रूप में भार। क्या यह एक उचित दृष्टिकोण की तरह लगता है?

यह एक कोर्सिंग के लिए एक प्रोग्रामिंग असाइनमेंट है जिसे मैं ले रहा हूं, इसलिए कृपया विचारों को चित्रित करने के लिए केवल वैचारिक चर्चा और/या छद्म कोड शामिल करें।

Answer 1

मुझे लगता है कि आपको इस तथ्य पर ध्यान देना चाहिए कि मशीन कपड़े को दो टुकड़ों में काट देती है। उन दो टुकड़ों में से प्रत्येक में क्या फिट हो सकता है? निम्नलिखित पर विचार करें:

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

ये चार कपड़े में फिट हैं, लेकिन तीन कटौती के साथ हासिल करने के लिए संभव नहीं है। (संभवतः एक अलग व्यवस्था से इन विशेष टुकड़ों के साथ अनुमति मिल जाएगी; इसे एक वैचारिक आरेख के रूप में सोचें, स्केल न करें। मेरे एसीआईआई कला कौशल आज सीमित हैं।)

"कट कहां है" पर ध्यान देना चाहिए गतिशील प्रोग्रामिंग समाधान। सौभाग्य।

Answer 2

तो आप X * Y आयताकार से शुरू करते हैं। मान लें कि इष्टतम समाधान में लंबवत (या क्षैतिज) कटौती शामिल है, तो आपके पास X * Y1 और X * Y2Y1 + Y2 = Y के साथ आयामों के साथ दो नए आयताकार हैं। चूंकि आप अपने लाभ को अधिकतम करना चाहते हैं, इसलिए आपको इन नए आयतों (इष्टतम प्रतिस्थापन) पर लाभ को अधिकतम करने की आवश्यकता है। तो आपका प्रारंभिक पुनरावृत्ति निम्नानुसार है: f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y))X1, X2 (क्षैतिज कट) और Y1, Y2 (लंबवत कट) के सभी मूल्यवान मानों के लिए।

अब सवाल है जब मैं वास्तव में उत्पाद बनाने का निर्णय लेता हूं? आप एक उत्पाद बनाने का निर्णय ले सकते हैं जब इसके आयामों में से एक आपके वर्तमान आयत के आयामों में से एक के बराबर होता है (क्यों? क्योंकि यदि यह नहीं है, और इष्टतम समाधान में यह उत्पाद शामिल है, तो जल्दी या बाद में आपको एक ऊर्ध्वाधर (या क्षैतिज) कटौती करें और यह मामला प्रारंभिक रिकर्सन में पहले ही संभाला जा चुका है), इसलिए आप उचित कटौती करते हैं और आपके पास उत्पाद प्राप्त करने के लिए किए गए कट के आधार पर एक नया आयत X * Y1 (या X1 * Y) है, इस मामले में रिकर्सन f(X, Y) = cost of product + f(X1, Y) बन जाता है।

मूल समस्या का समाधान f(X, Y) है। इस डीपी समाधान का चलने का समय O(X * Y * (X + Y + number of available products)) होगा: आपके पास X * Y संभावित आयताकार हैं, इनमें से प्रत्येक के लिए आप प्रत्येक संभावित कट (X + Y) आज़माते हैं और आप इस आयत से उपलब्ध उत्पादों में से एक को बनाने का प्रयास करते हैं।

इसके अलावा, इस समस्या को भी देखें: 2010 आईसीपीसी वर्ल्ड फाइनल से चॉकलेट साझा करना।

Answer 3

या (something, 0) के आयत के लिए आवश्यक शर्तों को Rect() फ़ंक्शन में शामिल करें।

Answer 4

अनुकूलन() {

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

}

अनुकूलन (एक्स, वाई, चौड़ाई, ऊंचाई, ज्ञापन) {

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 

}