Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

दिए गए पूर्णांकों से अधिकतम संभावित टैली ज्ञात करने का C++ प्रोग्राम


मान लीजिए हमें दो पूर्णांक n और m दिए गए हैं और k टपल्स हैं जिनमें चार पूर्णांक {ai, bi, ci, di} हैं। चार सरणियाँ a, b, c, d दी गई हैं जहाँ a[i] i-वें टपल का a मान दर्शाता है। अब एक अनुक्रम dp पर विचार करें जिसमें n धनात्मक पूर्णांक हों और 1 ≤ dp[1] < dp[2] < ... < dp[n] ≤ m। हम एक मेट्रिक 'टैली' परिभाषित करते हैं। टैली उन सभी सूचकांकों i के d[i] का योग है जहाँ dp[b[i]] - dp[a[i]] = c[i]। यदि ऐसा कोई i नहीं है तो टैली 0 होगी। हमें dp की अधिकतम संभावित टैली ज्ञात करनी है।

उदाहरण के लिए, यदि इनपुट है n = 4, m = 5, k = 4, a = {2, 2, 3, 5}, b = {4, 3, 4, 6}, c = {4, 3, 3, 4}, d = {110, 20, 20, 40}, तो आउटपुट 130 होगा।

चरण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

आकार 100 के सरणी A, B, C, D और आकार 10 के सरणी dp परिभाषित करें
एक फंक्शन depthSearch() परिभाषित करें जो c, l लेता है:
    यदि c == n, तो:
        total := 0
        i := 0 से k-1 तक:
            यदि dp[B[i]] - dp[A[i]] == C[i], तो:
                total := total + D[i]
        res := max(res, total)
        लौटें
    j := l से m तक:
        dp[c] := j
        depthSearch(c + 1, j)
i := 0 से k-1 तक:
    A[i] := a[i], B[i] := b[i], C[i] := c[i], D[i] := d[i]
    A[i] घटाएँ, B[i] घटाएँ
depthSearch(0, 1)
res लौटाएँ

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; int n, m, k, res = 0; int A[100], B[100], C[100], D[100], dp[10]; void depthSearch(int c, int l){ if(c == n){ int total = 0; for(int i = 0; i < k; i++) { if(dp[B[i]] - dp[A[i]] == C[i]) total += D[i]; } res = max(res, total); return; } for(int j = l; j <= m; j++){ dp[c] = j; depthSearch(c + 1, j); } } int solve(int a[], int b[], int c[], int d[]){ for(int i = 0; i < k; i++){ A[i] = a[i], B[i] = b[i], C[i] = c[i], D[i] = d[i]; A[i]--, B[i]--; } depthSearch(0, 1); return res; } int main() { n = 4, m = 5, k = 4; int a[] = {2, 2, 3, 5}, b[] = {4, 3, 4, 6}, c[] = {4, 3, 3, 4}, d[] = {110, 20, 20, 40}; cout<< solve(a, b, c, d); return 0; }

इनपुट

4, 5, 4, {2, 2, 3, 5}, {4, 3, 4, 6}, {4, 3, 3, 4}, {110, 20, 20, 40}

आउटपुट

130
  1. ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और edges सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक x मान है जो 1 से n के बीच होता है, यह values सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को सुपर वर्टेक्स कहा जाता है

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. ग्राफ से घटाए जा सकने वाले अधिकतम स्कोर की मात्रा ज्ञात करने का C++ प्रोग्राम ग्राफ से घटाए जा सकने वाले अधिकतम स्कोर की मात्रा ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक भारित, निदेश रहित ग्राफ दिया गया है। ग्राफ का स्कोर ग्राफ में सभी एज भारों का योग है। एज भार ऋणात्मक हो सकते हैं, और यदि उन्हें हटा दिया जाए तो ग्राफ का स्कोर बढ़ जाता है। हमें ग्राफ को संबद्ध रखते हुए एज हटाकर ग्राफ के स्कोर को न्यूनतम करना है। हमें घटाए जा सकन