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

C++ में विभाजन समान उपसमुच्चय योग


मान लीजिए कि हमारे पास एक गैर-रिक्त सरणी है जिसमें केवल सकारात्मक संख्याएं हैं, हमें यह पता लगाना होगा कि क्या सरणी को दो सबसेट में विभाजित किया जा सकता है जैसे कि दोनों सबसेट में तत्वों का योग समान है। तो अगर इनपुट [1,5,11,5] जैसा है, तो आउटपुट सही होगा। चूंकि इस सरणी को [1, 5, 5] और [11]

. के रूप में विभाजित किया जा सकता है

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

  • n :=सरणी का आकार
  • योग :=0
  • i के लिए:=0 से n - 1
    • योग :=योग + अंक[i]
  • यदि योग विषम है, तो झूठी वापसी करें
  • योग :=योग/2
  • साइज योग + 1 का डीपी नामक एक सरणी बनाएं
  • dp[0] :=सच
  • मैं के लिए 0 से n - 1 की सीमा में
    • x :=nums[i]
    • j के लिए:=j - x तक का योग
      • dp[j] :=dp[j] या dp[j - x], जो 0 नहीं है
  • रिटर्न डीपी[योग]

उदाहरण(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPartition(vector<int>& nums) {
      int n = nums.size();
      int sum = 0;
      for(int i =0;i<n;i++)sum+=nums[i];
      if(sum&1)return false;
      sum/=2;
      vector <bool> dp(sum+1);
      dp[0] = true;
      for(int i =0;i<n;i++){
         int x = nums[i];
         for(int j =sum;j-x>=0;j--){
            dp[j]=dp[j] || dp[j-x];
         }
      }
      return dp[sum];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,11,5};
   cout << ob.canPartition(v);
}

इनपुट

[1,5,11,5]

आउटपुट

1

  1. C++ में समान वृक्ष विभाजन

    मान लीजिए कि हमारे पास n नोड्स के साथ एक बाइनरी ट्री है, तो हमारा काम यह जांचना है कि क्या ट्री को दो पेड़ों में विभाजित करना संभव है, जिनका मूल पेड़ के ठीक एक किनारे को हटाने के बाद बराबर योग है। तो, अगर इनपुट पसंद है तब आउटपुट सही होगा। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - एक

  1. C++ में किसी सरणी का अधिकतम औसत योग विभाजन

    समस्या कथन एक सरणी को देखते हुए, हम संख्या A की एक पंक्ति को अधिकतम K आसन्न (गैर-रिक्त) समूहों में विभाजित करते हैं, फिर स्कोर प्रत्येक समूह के औसत का योग होता है। अधिकतम स्कोर क्या हो सकता है? उदाहरण यदि इनपुट सरणी {9, 2, 5, 3, 10} है तो हम सरणी को इस प्रकार विभाजित कर सकते हैं - {9} {2, 5, 3} औ

  1. सी ++ में विभाज्य योग?

    यहाँ हम देखेंगे कि विभाज्य योग क्या है? n का विभाज्य योग n को छोड़कर n के सभी पूर्ण गुणनखंडों का योग है। उदाहरण के लिए, यदि संख्या 20 है, तो पूर्ण गुणनखंड (1, 2, 4, 5, 10) हैं। तो विभाज्य योग 22 है। एक दिलचस्प तथ्य यह है कि, यदि किसी संख्या का विभाज्य योग ही वह संख्या है, तो वह संख्या एक पूर्ण संख्