डायनेमिक प्रोग्रामिंग एल्गोरिदम नॅपैकैक जावा कोड

Question

के समान एक मिशन-महत्वपूर्ण उत्पादन प्रणाली में एन चरण हैं जिन्हें अनुक्रमिक रूप से किया जाना है; मंच मैं मशीन M_i द्वारा किया जाता है।

प्रत्येक मशीन एम_आई में विश्वसनीयता के कामकाज की संभावना है और असफल होने की संभावना 1-r_i (और असफलता स्वतंत्र हैं)। इसलिए, यदि हम एक ही मशीन के साथ प्रत्येक चरण को लागू करते हैं, तो पूरी प्रणाली काम करने की संभावना r_1, r_2, ..., r_n है। इस संभावना को बेहतर बनाने के लिए हम मशीन I_i की m_i प्रतियां रखते हुए अनावश्यकता जोड़ते हैं जो चरण I करता है।

संभावना है कि सभी m_i प्रतियां एक साथ विफल हो जाएंगी (1-r_i)^(m_i), इसलिए संभावना है कि चरण सही ढंग से पूरा हो गया है 1- (1-r_i)^(मील) और संभावना है कि पूरे सिस्टम काम प्रोड (i = 1, n) {1- (1-r_i)^(m_i)} है।

प्रत्येक मशीन M_i की लागत c_i है, और मशीन खरीदने के लिए कुल बजट बी है। (मान लीजिए कि बी और सी_आई सकारात्मक पूर्णांक हैं।) जावा कोड में एल्गोरिदम लिखें जो संभाव्यता r_1, ..., r_n, लागत c_1, ..., c_n, और बजट बी को अनावश्यकता मिलती है, .. ।, m_n जो उपलब्ध बजट के भीतर हैं और यह संभावना है कि सिस्टम सही तरीके से काम करता है (अधिकतम विश्वसनीयता प्राप्त करने योग्य निर्धारित करें)। साथ ही, दिखाएं कि प्रत्येक प्रकार की कितनी मशीनें बजट के भीतर विश्वसनीय विश्वसनीयता को प्राप्त करती हैं।

तो मैंने एक ऐसी फाइल में पढ़ा जो मुझे कुल बजट की अनुमति देता है, मशीनों की संख्या के बाद, और उसके बाद मैं प्रत्येक मशीन के लिए लागत और विश्वसनीयता में पढ़ता हूं। मैं लागत और विश्वसनीयता को दो लिंक्ड सूची में संग्रहीत करता हूं (सुनिश्चित नहीं है कि यह सबसे अच्छा है)।

try { 
      BufferedReader newFileBuffer = new BufferedReader(new  FileReader(inputFile)); 
      budget = Integer.parseInt(newFileBuffer.readLine()); 
      numberOfMachines = Integer.parseInt(newFileBuffer.readLine()); 
      while ((fileLine = newFileBuffer.readLine()) != null) 
      {  
       line = fileLine.split(" "); 

       try 
       { 
        cost.add(Integer.parseInt(line[0])); 
        totalCostOfOneEach += Integer.parseInt(line[0]); 
        reliability.add(Float.parseFloat(line[1])); 
       } catch (NumberFormatException nfe) {}; 

      } 
      newFileBuffer.close(); 
     } catch (Exception e) 
     { 
      e.printStackTrace(); 
     } 

वहां से मुझे पता है कि प्रत्येक मशीन में से एक एक बार इस्तेमाल किया जाना चाहिए तो मैं कुल राशि से बजट यह प्रत्येक मशीन (totalCostOfOneEach) में से एक के लिए खर्च घटाना, यह मेरे बजट या अतिरेक बजट बचे देता है अगर तुम।

bRedundent = (budget - totalCostOfOneEach); 

अब जहां मैं अटक गया हूं, मैं समाधान खोजने के लिए क्या लूप करना चाहता हूं, इस पर खो गया हूं। मैं शोध किया है और इस solution पाया, लेकिन मैं लाइन

Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k} 

तो मैं क्या जानते हो मैं एक डबल सरणी बनाया है है समझ में नहीं आता है और मैं इतनी के रूप में सरणियों प्रारंभ:

double[][] finalRel = new double[numberOfMachines][bRedundent]; 
for (int j = 0; j < numberOfMachines; j++) 
{ 
    finalRel[0][j] = 0; 
} 

for (int b = 1; b < budget; b++) 
{ 
    finalRel[b][1] = reliability.get(0); 
} 

अब है जहां मैं फंस गया हूं, मेरा मानना ​​है कि मुझे मशीन की संख्या और फिर लागत पर लूप करना चाहिए लेकिन यह काम नहीं कर रहा है और मुझे पता है कि मुझे किसी भी तरह बजट शामिल करना होगा। तो यह मैं वर्तमान में है कि सब पर काम नहीं करता क्या है:

for (int i = 1; i < numberOfMachines; i++) 
{ 
    for (int c = cost.get(i); c < budget; c++) 
    { 
     finalRel[i][c] = Math.min(finalRel[i-1][c], finalRel[i-1][c - cost.get(numberOfMachines)]*(l)); 
    } 
} 

मैं जानता हूँ कि subproblem finalRel निरूपित किया जाता है [मैं, ख], मशीनों 1, 2 की सबसे विश्वसनीय विन्यास,। । । , मैं (प्रत्येक मशीन में से कम से कम एक) बजट बी के भीतर उपलब्ध है। वांछित उत्तर अंतिम होगा [एन, बी]।

और अगर हम बजट के तहत हैं तो पुनरावृत्ति, हम विश्वसनीयता 0 (जिसका अर्थ संभव नहीं है) वापस कर देते हैं। अगर हम बजट से बाहर हैं (बी = 0), लेकिन अभी भी मशीनें खरीदने की जरूरत है (i> 0), हम 0 लौटते हैं (सभी सीआई> 0 मान लें)। यदि मैं = 0, हमारे पास कोई मशीन नहीं है जिसे हमें खरीदना है, तो विश्वसनीयता 1 है (यदि यह 0 थी, तो सबकुछ 0 से गुणा हो जाएगा, जो कि अच्छा नहीं है)। यदि बजट छोड़ दिया गया है (बी> 0) और मशीनें खरीदने के लिए छोड़ दी गई हैं (i> 0), हम खरीदने के लिए मशीनों की सभी संभावनाओं की कोशिश करते हैं - हमें कम से कम एम ≥ 1 खरीदना है, और एम ≤ बी तक ≤ मंजिल (बी/सी_आई) ≤ बी ≤ बी, उनमें से। प्रत्येक मामले में, शेष बजट बी-एम · सी_आई होगा। मशीन 1 के लिए सबसे अच्छी विश्वसनीयता। । ।, i - 1 आरईएल [i - 1, बी - एम · सीआई] होगा, जिसे एम_आई, (1 - (1 - ri)^मीटर की एम प्रतियों के योगदान से गुणा किया जाना चाहिए या here सारांशित किया जाना चाहिए।

मुझे यह बहुत सारी जानकारी है, लेकिन मैं थोड़ी देर के लिए अटक गया हूं इसलिए किसी भी मदद की सराहना की जाती है।

Answer 1

आप उससे सरल पुनरावृत्ति के साथ काम कर सकते हैं। i = 0, ..., n और b = 0, ..., B के लिए, हम R(i, b)1 से चरण i चरण B पर उप-पाइपलाइन की अधिकतम विश्वसनीयता होने दें। मूल मामले

For b = 0, ..., B, 
    R(0, b) = 1, 

क्योंकि खाली पाइपलाइन कभी विफल नहीं होती है और कुछ भी लागत नहीं होती है। इसके बाद हम जुड़े हुए पुनरावृत्ति है, जो मैं स्पष्टता के लिए थोड़ा फिर से लिखा है है:

For i = 1, ..., n, 
    For b = 0, ..., B, 
    R(i, b) = max {R(i-1, b - k*c_i) * (1 - (1-r_i)^k) 
        for k = 0, ..., floor(b/c_i)}, 

जहां k चरण i मशीनों है कि हम खरीदने पर विचार कर रहे हैं की संख्या है (परिभाषित करने के मामले मशीनों में 0^0 = 1 पूरी तरह से विश्वसनीय हो सकता है, आपको चाहिए अपने आप को बिजली की गणना करें और फिर शक्ति को कम करें - गुणा को कम करें, जो इस समस्या को हल करता है और प्रदर्शन में सुधार करता है)। कारक (1 - (1-r_i)^k) मशीनों के साथ चरण i की विश्वसनीयता है। कारक R(i-1, b - k*c_i) अवशिष्ट बजट दिए गए पिछले चरणों की अधिकतम विश्वसनीयता है। सीमा floor(b/c_i) चरण i मशीनों की अधिकतम संख्या है जो कुल में b पर खर्च करती है।