C++ में अधिकतम अवकाश दिवस

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

• हम केवल N शहरों के बीच यात्रा कर सकते हैं; उन्हें 0 से N-1 तक अनुक्रमित द्वारा दर्शाया जाता है। सबसे पहले, हम सोमवार को 0 अनुक्रमित शहर में हैं।

• ये शहर उड़ानों से जुड़े हुए हैं। उड़ानों का प्रतिनिधित्व करने के लिए हमारे पास एक एन एक्स एन मैट्रिक्स (जरूरी नहीं कि सममित) है। शहर i से शहर j तक एयरलाइन की स्थिति का प्रतिनिधित्व करने वाली उड़ानें। यदि शहर i से शहर j के लिए कोई उड़ान नहीं है, तो मैट्रिक्स उड़ानें[i][j] 0 होगी; अन्यथा, उड़ानें[i][j] =1. साथ ही, सभी i के लिए उड़ानें[i][i] =0।

• हमारे पास यात्रा करने के लिए K सप्ताह हैं। हम प्रति दिन केवल एक बार उड़ान भर सकते हैं और केवल प्रत्येक सप्ताह के सोमवार की सुबह उड़ान भर सकते हैं।

• प्रत्येक शहर के लिए, हमारे पास अलग-अलग सप्ताहों में केवल अवकाश के दिनों को प्रतिबंधित किया जा सकता है, इसके लिए हमारे पास एक N*K मैट्रिक्स है जिसे दिन कहा जाता है जो इस संबंध को दिखा रहा है। दिनों के मूल्य के लिए [i] [j], यह उस अधिकतम दिनों को दर्शाता है जब हम शहर में सप्ताह में छुट्टी ले सकते हैं।

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

इसलिए, यदि इनपुट उड़ानों की तरह है =[[0,1,1], [1,0,1], [1,1,0]], दिन =[[1,3,1], [6,0 ,3],[3,3,3]], तो आउटपुट 12 होगा

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

• n :=उड़ानों की पंक्तियाँ

• मी :=दिनों मैट्रिक्स के कॉलम

• एक 2D सरणी dp आकार (m + 1) x n

  . को परिभाषित करें

• इनिशियलाइज़ करने के लिए i :=m-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −

  करें

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • इनिशियलाइज़ k :=0 के लिए, जब k

      • यदि j, k के समान है या उड़ानें[j, k] शून्य नहीं है, तो -

        • dp[i, j] :=अधिकतम dp[i, j] और दिन[j, i] + dp[i + 1, k]

• रिट:=डीपी [0, 0]

• इनिशियलाइज़ करने के लिए मैं :=1, जब i

  • अगर उड़ानें [0, i] शून्य नहीं हैं, तो -

    • ret :=अधिकतम रिट और dp[0, i]

• वापसी रिट

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

उदाहरण

#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;
   }
};
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