अधिकतम राशि कम एम

Question

को देखते हुए की तुलना में: पूर्णांकों का सरणी मूल्य कश्मीर, एम

प्रश्न: अधिकतम राशि है जो हम दिया सरणी के सभी कश्मीर तत्व सबसेट से प्राप्त कर सकते हैं का पता लगाएं जैसे कि राशि मूल्य एम से कम है?

क्या इस समस्या के लिए कोई गतिशील प्रोग्रामिंग समाधान उपलब्ध नहीं है? या यदि यह केवल डीपी है [i] [j] [k] केवल इस प्रकार की समस्या को हल कर सकता है! क्या आप कृपया एल्गोरिदम समझा सकते हैं।

Answer 1

यह बस्ता या सबसेट-समस्या है, जहां समय के संदर्भ में (कीमत पर का एक प्रकार है खोज करने के लिए एक वृक्ष संरचना, उम्मीद है कि बहुत कम संयोजनों के साथ देता है इनपुट आकार बढ़ने के साथ घातीय बढ़ती अंतरिक्ष आवश्यकताओं की), गतिशील प्रोग्रामिंग सबसे प्रभावी तरीका है जो इस समस्या को सही हल करती है। अपने प्रश्न के लिए Is this variant of the subset sum problem easier to solve? देखें।

हालांकि, चूंकि आपकी समस्या बिल्कुल वही नहीं है, इसलिए मैं एक स्पष्टीकरण प्रदान करूंगा। dp[i][j] = true, यदि लंबाई i का उप-समूह है जो j और false पर है, तो वहां नहीं है। विचार यह है कि dp[][] प्रत्येक संभावित लंबाई के लिए सभी संभावित सबसेट्स की रकम एन्कोड करेगा।इसके बाद हम सबसे बड़े j <= M को देख सकते हैं जैसे कि dp[K][j]true है। हमारा बेस केस dp[0][0] = true क्योंकि हम हमेशा एक सबसेट बना सकते हैं जो आकार 0 में से किसी एक को चुनकर 0 पर रकम कर सकता है।

पुनरावृत्ति भी काफी सरल है। मान लीजिए कि हमने सरणी के पहले n मानों का उपयोग करके dp[][] के मानों की गणना की है। सरणी के पहले n+1 मानों के सभी संभावित सबसेट खोजने के लिए, हम बस n+1 _ वें मान ले सकते हैं और इसे पहले देखे गए सभी सबसेट में जोड़ सकते हैं। अधिक ठोस रूप से, हमारे पास निम्न कोड है:

initialize dp[0..K][0..M to false 
dp[0][0] = true 
for i = 0 to N: 
    for s = 0 to K - 1: 
     for j = M to 0: 
      if dp[s][j] && A[i] + j < M: 
       dp[s + 1][j + A[i]] = true 
for j = M to 0: 
    if dp[K][j]: 
     print j 
     break 

Answer 2

हम K तत्वों का एक सबसेट ढूंढ रहे हैं जिसके लिए तत्वों का योग अधिकतम है, लेकिन M से कम है।

हम निम्नानुसार सबसेट में सबसे बड़े तत्व पर [X, Y] सीमाएं रख सकते हैं।

सबसे पहले हम (0) पूर्णांक, values[0] ... values[N-1] को सॉर्ट करते हैं, तत्व values[0] सबसे छोटा है।

कम बाध्य X जो

values[X] + values[X-1] + .... + values[X-(K-1)] < M के लिए सबसे बड़ा पूर्णांक है।

(यदि XN-1 है, तो हम इस सवाल का जवाब मिल गया है।)

ऊपरी बाध्य Y सबसे बड़ा पूर्णांक से भी कम समय N है जो

values[0] + values[1] + ... + values[K-2] + values[Y] < M के लिए।

इस अवलोकन के साथ

, अब हम उच्चतम अवधि Z, जहां

X <= Z <= Y के प्रत्येक मान के लिए दूसरी सबसे अधिक अवधि के लिए बाध्य कर सकते हैं।

हम ठीक उसी विधि का उपयोग कर सकते हैं, क्योंकि समस्या का रूप बिल्कुल वही है। values[0] ... values[Z-1] से ली गई K-1 तत्वों का एक सबसेट कम हो रहा है, जिसके लिए तत्वों का योग अधिकतम है, लेकिन M - values[Z] से कम है।

एक बार हमने को वैल्यू को बाध्य कर दिया है, तो हम दो उच्चतम मानों की प्रत्येक जोड़ी के लिए तीसरे सबसे बड़े मूल्य पर सीमा डाल सकते हैं। और इसी तरह।

यह हमें एन से खोज करने के लिए चुनें लालकृष्ण

Answer 3

फ़ेलिक्स सही है कि यह knapsack समस्या का एक विशेष मामला है। उनके गतिशील प्रोग्रामिंग एल्गोरिदम ओ (के * एम) आकार और ओ (के * के * एम) समय की मात्रा लेता है। मेरा मानना ​​है कि वेरिएबल एन का उपयोग वास्तव में के।

नापसंद समस्या के लिए समर्पित दो पुस्तकें हैं। केलेरर, पर्सची और पिसिंगर [2004, स्प्रिंगर-वेरलाग, आईएसबीएन 3-540-40286-1] द्वारा नवीनतम पृष्ठ, उनके पृष्ठ 76 पर एक बेहतर गतिशील प्रोग्रामिंग एल्गोरिदम प्रदान करता है, चित्रा 4.2 जो ओ (के + एम) स्पेस लेता है और ओ (केएम) समय, जो फ़ेलिक्स द्वारा दिए गए गतिशील प्रोग्रामिंग एल्गोरिदम की तुलना में भारी कमी है। ध्यान दें कि पुस्तक की एल्गोरिदम की अंतिम पंक्ति पर एक टाइपो है जहां यह सी-बार होना चाहिए: = सी-बार - w_ (आर (सी-बार))।

मेरा सी # कार्यान्वयन नीचे है। मैं यह नहीं कह सकता कि मैंने इसका व्यापक परीक्षण किया है, और मैं इस पर प्रतिक्रिया का स्वागत करता हूं। मैंने पुस्तक में एल्गोरिदम में दिए गए सेट की अवधारणा को लागू करने के लिए BitArray का उपयोग किया था। मेरे कोड में, c क्षमता है (जो मूल पोस्ट में एम कहा जाता था), और मैंने वजन रखने वाले सरणी के रूप में A के बजाय w का उपयोग किया।

इसके उपयोग का एक उदाहरण है:

int[] optimal_indexes_for_ssp = new SubsetSumProblem(12, new List<int> { 1, 3, 5, 6 }).SolveSubsetSumProblem(); 

जहां सरणी optimal_indexes_for_ssp शामिल हैं [0,2,3] तत्वों 1, 5, 6.

using System; 
using System.Collections.Generic; 
using System.Collections; 
using System.Linq; 

public class SubsetSumProblem 
{ 
    private int[] w; 
    private int c; 

    public SubsetSumProblem(int c, IEnumerable<int> w) 
    { 
     if (c < 0) throw new ArgumentOutOfRangeException("Capacity for subset sum problem must be at least 0, but input was: " + c.ToString()); 
     int n = w.Count(); 
     this.w = new int[n]; 
     this.c = c; 
     IEnumerator<int> pwi = w.GetEnumerator(); 
     pwi.MoveNext(); 
     for (int i = 0; i < n; i++, pwi.MoveNext()) 
     this.w[i] = pwi.Current; 
    } 

    public int[] SolveSubsetSumProblem() 
    { 
     int n = w.Length; 
     int[] r = new int[c+1]; 
     BitArray R = new BitArray(c+1); 
     R[0] = true; 
     BitArray Rp = new BitArray(c+1); 
     for (int d =0; d<=c ; d++) r[d] = 0; 
     for (int j = 0; j < n; j++) 
     { 
     Rp.SetAll(false); 
     for (int k = 0; k <= c; k++) 
      if (R[k] && k + w[j] <= c) Rp[k + w[j]] = true; 
     for (int k = w[j]; k <= c; k++) // since Rp[k]=false for k<w[j] 
      if (Rp[k]) 
      { 
      if (!R[k]) r[k] = j; 
      R[k] = true; 
      } 
     } 
     int capacity_used= 0; 
     for(int d=c; d>=0; d--) 
     if (R[d]) 
     { 
      capacity_used = d; 
      break; 
     } 
     List<int> result = new List<int>(); 
     while (capacity_used > 0) 
     { 
     result.Add(r[capacity_used]); 
     capacity_used -= w[r[capacity_used]]; 
     } ; 
     if (capacity_used < 0) throw new Exception("Subset sum program has an internal logic error"); 
     return result.ToArray(); 
    } 
}