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

C++ में अधिकतम छुट्टी दिन


मान लीजिए एक कंपनी अपने सर्वश्रेष्ठ कर्मचारियों में से एक को N शहरों के बीच यात्रा करके कुछ संसाधन एकत्र करने का विकल्प देना चाहती है। लेकिन कर्मचारी कुछ छुट्टियां भी चाहते हैं, हम कुछ विशेष शहरों और हफ्तों में छुट्टियां ले सकते हैं। हमारा कार्य यात्रा को इस तरह शेड्यूल करना है कि हम K हफ्तों के दौरान अधिकतम छुट्टी के दिन ले सकें, लेकिन कुछ नियम और प्रतिबंध हैं जिनका हमें पालन करना होगा।

  • हम केवल N शहरों के बीच यात्रा कर सकते हैं; वे 0 से N-1 तक के इंडेक्स द्वारा दर्शाए जाते हैं। सबसे पहले, हम सोमवार को इंडेक्स 0 वाले शहर में होते हैं।
  • ये शहर उड़ानों से जुड़े हुए हैं। हमारे पास एक N x N मैट्रिक्स (जरूरी नहीं कि सममित) है जो उड़ानों को दर्शाता है। flights[i][j] शहर i से शहर j तक एयरलाइन की स्थिति दर्शाता है। यदि शहर i से शहर j तक कोई उड़ान नहीं है, तो मैट्रिक्स flights[i][j] 0 होगा; अन्यथा, flights[i][j] = 1। साथ ही, सभी i के लिए flights[i][i] = 0।
  • हमारे पास यात्रा के लिए K हफ्ते हैं। हम प्रति दिन अधिकतम एक बार उड़ान ले सकते हैं और केवल प्रत्येक हफ्ते के सोमवार की सुबह उड़ान ले सकते हैं।
  • प्रत्येक शहर के लिए, हम अलग-अलग हफ्तों में केवल प्रतिबंधित छुट्टी के दिन ले सकते हैं, इसके लिए हमारे पास N*K मैट्रिक्स days है जो इस संबंध को दर्शाता है। days[i][j] के मान के लिए, यह शहर i में हफ्ते j में हम अधिकतम कितने दिन छुट्टी ले सकते हैं, दर्शाता है।

इसलिए यदि हमारे पास flights मैट्रिक्स और days मैट्रिक्स है, और हमें K हफ्तों के दौरान हम जितने अधिकतम छुट्टी के दिन ले सकते हैं, आउटपुट करना है।

इसलिए, यदि इनपुट flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] जैसा है, तो आउटपुट 12 होगा।

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

  • n := flights की पंक्तियाँ
  • m := days मैट्रिक्स के कॉलम
  • आकार (m+1) x n का एक 2D सरणी dp परिभाषित करें
  • i := m-1 से 0 तक घटाते हुए लूप चलाएं:
    • j := 0 से n-1 तक लूप चलाएं:
      • k := 0 से n-1 तक लूप चलाएं:
        • यदि j == k या flights[j][k] शून्येतर है, तो:
          • dp[i][j] := max(dp[i][j], days[j][i] + dp[i+1][k])
  • ret := dp[0][0]
  • i := 1 से n-1 तक लूप चलाएं:
    • यदि flights[0][i] शून्येतर है, तो:
      • ret := max(ret, dp[0][i])
  • ret वापस करें

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

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
class Solution { 
public: 
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) { 
        int n = flights.size(); 
        int m = days[0].size(); 
        vector<vector<int> > dp(m + 1, vector<int>(n)); 
        for (int i = m - 1; i >= 0; i--) { 
            for (int j = 0; j < n; j++) { 
                for (int k = 0; k < n; k++) { 
                    if (j == k || flights[j][k]) { 
                        dp[i][j] = max(dp[i][j], days[j][i] + dp[i + 1][k]); 
                    } 
                } 
            } 
        } 
        int ret = 0; 
        ret = dp[0][0]; 
        for (int i = 1; i < n; i++) { 
            if (flights[0][i]) { 
                ret = max(ret, dp[0][i]); 
            } 
        } 
        return ret; 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<vector<int>> v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}; 
    cout << (ob.maxVacationDays(v1, v2)); 
}

इनपुट

v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}

आउटपुट

12
  1. - C++ में अधिकतम अंतराल

    मान लीजिए हमारे पास एक सरणी है, जो क्रमबद्ध नहीं है। हमें इसके क्रमबद्ध रूप में क्रमिक तत्वों के बीच अधिकतम अंतर ढूंढना है। यदि सरणी में 2 से कम तत्व हैं तो हम 0 लौटाएंगे। तो यदि सरणी [12,3,9,1,17] जैसी है, तो आउटपुट 6 होगा, क्योंकि क्रमबद्ध सरणी [1,3,9,12,17] होगी तो 5 अधिकतम अंतर होगा क्योंकि 3 और

  1. - C++ में मैक्सिमम विड्थ रैम्प (Maximum Width Ramp)

    मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, एक रैम्प (i, j) का एक टपल है जिसके लिए i < j और A[i] ≤ A[j]। ऐसे रैम्प की चौड़ाई j - i होती है। हमें A में रैम्प की अधिकतम चौड़ाई खोजनी है। यदि कोई नहीं है, तो 0 लौटाएं। उदाहरण के लिए, यदि इनपुट [6,0,8,2,1,5] है, तो आउटपुट 4 होगा। यहां अधिकतम चौड़ाई रै

  1. - C++ में चतुर्भुज का अधिकतम क्षेत्रफल

    समस्या कथन चतुर्भुज की चार भुजाएं a, b, c, d दी गई हैं, दी गई भुजाओं से बनने वाले चतुर्भुज का अधिकतम क्षेत्रफल ज्ञात करें। एल्गोरिदम हम इस समस्या को हल करने के लिए ब्रह्मगुप्त के सूत्र का उपयोग कर सकते हैं: √((s-a)(s-b)(s-c)(s-d)) उपरोक्त सूत्र में s अर्ध-परिमाप है। इसकी गणना निम्नानुसार की जाती ह